Python 版代码
树状数组
时间复杂度
$O(log\ n)$
3300 ms
Python 代码
n, m = map(int, input().split(' '))
tr = [0 for i in range(n+1)] # tree
a = [0]
a += list(map(int, input().strip().split(' ')))
def lowbit(x):
return x & -x
# 元素修改
def add(x, v):
i = x
while i <= n:
tr[i] += v
i += lowbit(i)
# 查询,求和
def query(x):
res = 0
i = x
while i:
res += tr[i]
i -= lowbit(i)
return res
for i in range(1, n+1):
add(i, a[i])
while m:
m -= 1
k, x, y = map(int, input().split(' '))
if k:
add(x, y)
else:
print(query(y) - query(x-1))
线段树
时间复杂度
$O(log\ n)$
6994 ms
Python 代码
n, m = map(int, input().split(' '))
a = [0]
a += list(map(int, input().strip().split(' ')))
class Node():
def __init__(self):
self.l = 0
self.r = 0
self.sum_ = 0
# pushup:用子节点信息更新当前节点信息
def pushup(u):
tr[u].sum_ = tr[u<<1].sum_ + tr[u<<1|1].sum_
# build:在一端区间上初始化线段树
def build(u, l, r):
if l == r:
tr[u].l = l
tr[u].r = r
tr[u].sum_ = a[r]
else:
tr[u].l = l
tr[u].r = r
mid = l + r >> 1
build(u<<1, l, mid), build(u<<1|1, mid+1, r)
pushup(u)
# modify:单点修改
def modify(u, x, v):
if tr[u].l == tr[u].r:
tr[u].sum_ += v
else:
mid = tr[u].l + tr[u].r >> 1
if x <= mid:
modify(u<<1, x, v)
else:
modify(u<<1|1, x, v)
pushup(u)
# query:查询,求和
def query(u, l, r):
if tr[u].l >= l and tr[u].r <= r:
return tr[u].sum_
mid = tr[u].l + tr[u].r >> 1
sum_ = 0
if l <= mid:
sum_ = query(u<<1, l, r)
if r > mid:
sum_ += query(u<<1|1, l ,r)
return sum_
tr = [Node() for i in range(n*4)] # tree
build(1, 1, n)
while m:
m -= 1
k, a, b = map(int, input().strip().split(' '))
if k:
modify(1, a, b) # 根节点编号为 1
else:
print(query(1, a, b))
确实树状数组比线段树快了两倍
(Python 真的好慢啊 o(╥﹏╥)o)