AcWing 1264. 动态求连续区间和-python树状数组模板
原题链接
简单
作者:
雨牧羽折
,
2024-04-09 18:40:15
,
所有人可见
,
阅读 9
python 代码
#n<=10^5 nlogn 且需要单点修改+区间查询
n,m = map(int,input().split())
b = [0] + list(map(int,input().split()))
a = [0]*(n+1)
c = [0]*(n+1)
def lowbit(x):
return x&-x
for i in range(1,n+1):
a[i] = a[i-1] + b[i]
c[i] = a[i] - a[i-lowbit(i)]
def add(x,k):
while x<=n:
c[x] += k
x += lowbit(x)
def getSum(x):
res = 0
while x:
res += c[x]
x -= lowbit(x)
return res
for i in range(m):
k,a,b = map(int,input().split())
if k:
add(a,b)
else:
print(getSum(b)-getSum(a-1))