目录
功能
实现
Q:但是，c[x]左端点怎么确定呢？
Q:那么为什么要以二进制为基础呢？
Q:为什么是补码' - '？
区间查询
树形态
性质1.对于x<=y,要么c[x]和c[y]不交，要么c[x]包含于c[y]
性质2.c[x] 真包含 于c[x + lowbit(x)]
节点性质：
1. u < fa[u]
2. u大于任何一个u的后代，小于任何一个u的祖先
3. u的lowbit 严格小于 fa[u]的lowbit编辑
4. 点x的高度是log( lowbit(x) ,2),即x二进制最低位1的位数k
5. c[u]真包含于c[fa[u]]
6. c[u]真包含于c[v],其中v是u的任一祖先（反过来就是“真包含”、“任一后代”）
7. 对于任意v'>u，若v'不是u的祖先，则c[u] 和c[v']不相交
8. 对于任意v>u，当且仅当v是u的祖先，c[u]真包含于c[v]。这是单点修改的核心原理
9. u=s*2**(k+1) + 2**k时，其儿子数量为k : log( lowbit(u) ,2)
10. u的所有儿子对应c的管辖区间恰好拼接成 [ l(u) , u-1 ]
单点修改
区间加
对a数组进行区间加如何维护树状数组
如何单点查询
模版代码
P3374 单点操作+区间查询
P3368 区间加+单点查询
注：本文的图文是以oiwiki为基础，oiwiki是一个非常好的开源算竞项目
功能
树状数组做的，线段树都能做，但是线段树代码更短，而且时常更小
树状数组主要用于单点修改、区间查询
要求应用对象满足结合律和可差分
实现
从图中可以发现，c[x]管辖的区间一定是x为右端点
查询过程
Q:但是，c[x]左端点怎么确定呢？
树状数组是以二进制为基础的分解，规定c[x]管辖区间长度为2**k
Q:那么为什么要以二进制为基础呢？
计算机内部是二进制存储，二进制可以非常快速且自然地对应区间划分和合并，操作还能使用按位运算
以二进制为划分基础，那么位置x管理的就是长度为lowbit(x)的区间，而且划分是连续的，所以可以直接向加减lowbit(x)从而在父子间跳跃
注意：lowbit不是位数，而是位数对应的2**k
python里面就是与上自身的补码
def lowbit(x):return x & -xQ:为什么是补码' - '？
计算机的负数是用补码表示的，补码的过程是取反加1:
0001100为例：
取反 1110011
加一 1110100
区间查询
可以看出补码保留了原码中最低位的1的位置，与运算后得到1<<k，这就是我们需要的划分区间
回到数组c的左端点这个问题：c[x]管辖的是 a[x - lowbit(x) + 1:x+1] 左闭右开
那么查询 a数组的区间，就是不断的跳跃x -> x - lowbit(x) ，不断加上c[x]
def getsum(x): # a[1]..a[x]的和ans = 0while x > 0:ans = ans + c[x]x = x - lowbit(x)return ans树形态
我们设定：
左端点 l(x) = x - lowbit(x) + 1
x = s*2**(k+1) + 2**k 其中2**k即1<<k = lowbit(x)
数组c的相交、包含关系是他们对于a的管辖区间之间的关系
性质1.对于x<=y,要么c[x]和c[y]不交，要么c[x]包含于c[y]
性质2.c[x] 真包含 于c[x + lowbit(x)]
性质3.对于任意x<y<x+lowbit(x)，有c[x]和c[y]不交
设定fa[u]表示u的直系父亲
节点性质：
1. u < fa[u]
2. u大于任何一个u的后代，小于任何一个u的祖先
3. u的lowbit 严格小于 fa[u]的lowbit
4. 点x的高度是log( lowbit(x) ,2),即x二进制最低位1的位数k
5. c[u]真包含于c[fa[u]]
6. c[u]真包含于c[v],其中v是u的任一祖先（反过来就是“真包含”、“任一后代”）
7. 对于任意v'>u，若v'不是u的祖先，则c[u] 和c[v']不相交
8. 对于任意v>u，当且仅当v是u的祖先，c[u]真包含于c[v]。这是单点修改的核心原理
9. u=s*2**(k+1) + 2**k时，其儿子数量为k : log( lowbit(u) ,2)
10. u的所有儿子对应c的管辖区间恰好拼接成 [ l(u) , u-1 ]
单点修改
修改a[x]，我们的目标就是维护c数组，具体来说是管辖a[x]的c[y]
从树形态上看，y是x的祖先，所以我们就是跳跃父亲来修改c
def add(x, k):while x <= n: # 不能越界c[x] = c[x] + kx = x + lowbit(x)def mul(x, k):while x <= n: # 不能越界c[x] = c[x] * kx = x + lowbit(x)区间加
想要进行区间加，得用两个树状数组维护差分数组
设原数组的差分数组d[ i ] = a[ i ] - a[ i-1 ]
那么a[i] = d的前缀和[ i ]
由于d[ i ]的前缀和和d[ i ]*i 的前缀和并没有数学关系，所以得用两个树状数组分别维护 d[ i ] 和 d[ i ]*i
对a数组进行区间加如何维护树状数组
如何单点查询
由于d是a的差分，那么直接求d的前缀和即可
t1 = [0] * MAXN
t2 = [0] * MAXN
n = 0def lowbit(x):return x & (-x)def add(k, v):v1 = k * vwhile k <= n:t1[k] = t1[k] + vt2[k] = t2[k] + v1k = k + lowbit(k)def getsum(t, k):ret = 0while k:ret = ret + t[k]k = k - lowbit(k)return retdef add1(l, r, v):add(l, v)add(r + 1, -v)def getsum1(l, r):return ((r) * getsum(t1, r)- l * getsum(t1, l - 1)- (getsum(t2, r) - getsum(t2, l - 1)))模版代码
P3374 单点操作+区间查询
P3374 【模板】树状数组 1 - 洛谷
n,m=map(int,input().split())l=list(map(int,input().split()))def lowbit(x):return x & -xdef getsum(x): # a[1]..a[x]的和ans = 0while x > 0:ans = ans + c[x]x = x - lowbit(x)return ansdef add(x, k):while x <= n: # 不能越界c[x] = c[x] + kx = x + lowbit(x)#初始化
c=[0]*(n+1) #注意add中可以观察得树状数组一般下标从1开始
for i in range(1,n+1):add(i,l[i-1])for i in range(m):f,p,q=map(int,input().split())#不要用a，b，c。会和数组名重复if f==1:add(p,q)else:print(getsum(q)-getsum(p-1))#题目要求左闭右闭，那么就要b-1
P3368 区间加+单点查询
差分
n, m = map(int, input().split())
l = list(map(int, input().split()))def lowbit(x):return x & -xdef getsum(x):ans = 0while x > 0:ans += c[x]x -= lowbit(x)return ansdef add(x, k):while x <= n:c[x] += kx += lowbit(x)# 初始化
c = [0] * (n + 2) # 要开到n+1，因为有add(y+1)
for i in range(1, n+1):add(i, l[i-1])add(i+1, -l[i-1])for _ in range(m):op = list(map(int, input().split()))if op[0] == 1:x, y, k = op[1], op[2], op[3]add(x, k)add(y+1, -k)else:x = op[1]print(getsum(x))