网站做推广下载优化大师安装桌面

目录

功能

实现

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 < a=""> <>

节点性质：

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 & -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 ]

由于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))