Loading...
什么是前缀和?如果有一段长度为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&...