题目描述
求一个一维区间内的和
思想
对于一个数组:a1,a2,a3……an这个原数组
前缀和数组Si = a1+a2+……ai;S0 = 0
① 如何求Si:
for(i=1;i<=n;i++){
S[i] = S[i-1] + ai
}
② Si的作用:快速得求原数组中[l,r]的和;常规就是o(n),可以利用前缀和转换为S[r]-S[l-1] =>o(1)复杂度
算[1-10]即S[10] - S[0];由于S[0]=0,因此== S[10]
(前缀和) $O(max(m,n))$
算前缀和就是o(n),有m个询问,每次询问查询只需要O(1)就是o(m);因此总的是线性级别
参考文献
https://www.acwing.com/file_system/file/content/whole/index/content/163764/
python 代码
# 1.输入
N = 100010
n,m = map(int,input().split())
a = [0] + list(map(int,input().split())) # 因为要从a1开始有效因此多加了一个0
s = [0 for i in range(N)]
# 2.得到前缀和
for i in range(1,n+1):
s[i] = s[i-1] + a[i]
# 3.查询区间和
while m:
l,r = map(int,input().split())
print(s[r]-s[l-1])
m-=1
或者如下
n,m = map(int,input().split())
re = [0] + list(map(int,input().split()))
for i in range(1,n+1):
re[i] += re[i-1]
for i in range(m):
L,R = map(int,input().split())
print(re[R]-re[L-1])