Articles under the label of 前缀和

前缀和，差分

什么是前缀和？如果有一段长度为N的序列a[0:N-1]，然后给你m的询问，每次询问给出一个区间[L,R],要求你求出区间内的和，请问你会怎么做？暴力做法(时间复杂度为O(n*m))每次都遍历一遍它给的区间，计算出答案，这样子的方法固然没错，但是其时间复杂度达到了O(n*m)，如果数据量稍微大一点(1e5)就有可能超时前缀和(时间复杂度O(n+m))a[0]=0; for(int i=1;i&...