树状数组底层逻辑探讨 / 模版代码-P3374-P3368

目录

功能

实现

Q:但是，c[x]左端点怎么确定呢？

Q:那么为什么要以二进制为基础呢？

Q:为什么是补码' - '？

区间查询

树形态

性质1.对于x<=y,要么c[x]和c[y]不交，要么c[x]包含于c[y]

性质2.c[x] 真包含 于c[x + lowbit(x)]

性质3.对于任意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 区间加+单点查询

---

功能

树状数组做的，线段树都能做，但是线段树代码更短，而且时常更小

树状数组主要用于单点修改、区间查询

要求应用对象满足结合律和可差分

实现

从图中可以发现，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 & -x

Q:为什么是补码' - '？

计算机的负数是用补码表示的，补码的过程是取反加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 ]

这样我们就把目标数组a的区间和转换为两个数组的区间和

由于d[ i ]的前缀和和d[ i ]*i 的前缀和并没有数学关系，所以得用两个树状数组分别维护 d[ i ] 和 d[ i ]*i

对a数组进行区间加如何维护树状数组

那么操作如下：

1. d[ l ]单点加 val，然后d [ r+1 ]单点加 -val（保证不影响区间外面）

2. d*i数组[ l ]单点加 val * l，[ r+1 ]单点加 -val*( r+1 )

这样我们就将一个区间的操作转换为单点操作，才能应用到树状数组上

如何单点查询

由于d是a的差分，那么直接求d的前缀和即可

def lowbit(x):return x & -xdef init(a, tree1, tree2, n): #从数组a初始化d数组和d*i数组for i in range(1, n + 1):delta = a[i] - a[i - 1]add(tree1, n, i, delta)add(tree2, n, i, delta * (i - 1))def add(tree, n, x, v):  #树状数组单点操作while x <= n:tree[x] += vx += lowbit(x)def query(tree, x):  #树状数组区间查询（前缀和）#可用于d数组前缀和实现数组a的单点查询res = 0while x > 0:res += tree[x]x -= lowbit(x)return resdef range_add(tree1, tree2, n, l, r, v):  #区间操作add(tree1, n, l, v)             #操作1add(tree1, n, r + 1, -v)add(tree2, n, l, v * (l - 1))   #操作2add(tree2, n, r + 1, -v * r)def prefix_sum(tree1, tree2, x):    #数组a从1到x区间的前缀和return query(tree1, x) * x - query(tree2, x)def range_sum(tree1, tree2, l, r):  #数组a从l到r区间的和return prefix_sum(tree1, tree2, r) - prefix_sum(tree1, tree2, l - 1)

注意

数组a的下标是从1开始的，所以在初始化的时候记得前面加个元素，比如

a=[0]+list(map(int,input().split()))

并且两个树状数组也要开大一点，最好是 *(n+2) 

模版代码

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 区间加+单点查询

P3368 【模板】树状数组 2 - 洛谷

套用区间操作模板代码

def lowbit(x):return x & -xdef init(a, tree1, tree2, n): #从数组a初始化d数组和d*i数组for i in range(1, n + 1):delta = a[i] - a[i - 1]add(tree1, n, i, delta)add(tree2, n, i, delta * (i - 1))def add(tree, n, x, v):  #树状数组单点操作while x <= n:tree[x] += vx += lowbit(x)def query(tree, x):  #树状数组从1到x区间的前缀和查询res = 0while x > 0:res += tree[x]x -= lowbit(x)return resdef range_add(tree1, tree2, n, l, r, v):  #区间操作add(tree1, n, l, v)             #操作1add(tree1, n, r + 1, -v)add(tree2, n, l, v * (l - 1))   #操作2add(tree2, n, r + 1, -v * r)def prefix_sum(tree1, tree2, x):    #数组a从1到x区间的前缀和return query(tree1, x) * x - query(tree2, x)def range_sum(tree1, tree2, l, r):  #数组a从l到r区间的和return prefix_sum(tree1, tree2, r) - prefix_sum(tree1, tree2, l - 1)n,m=map(int,input().split())a=[0]+list(map(int,input().split())) #下标从1开始t1=[0]*(n+2)
t2=[0]*(n+2)
init(a,t1,t2,n)for _ in range(m):te=tuple(map(int,input().split()))#用tuple方便解包if te[0]==1:l,r,v=te[1:]range_add(t1,t2,n,l,r,v)else:idx=te[1]val=range_sum(t1,t2,idx,idx)print(val)

然而有小点会T和M，这是因为这段代码直接用区间查询的方式来单点查询

正确的做法是直接用前缀和单点查询

for _ in range(m):te=tuple(map(int,input().split()))#用tuple方便解包if te[0]==1:l,r,v=te[1:]range_add(t1,t2,n,l,r,v)else:idx=te[1]val=query(t1,idx)print(val)