AcWing 1264. 动态求连续区间和 ，详细讲解线段树与树状数组（Python，篇二）

   上一篇博客主要讲了线段树AcWing 1264. 动态求连续区间和 ，详细讲解线段树与树状数组（Python，篇一），那么本篇博客主要介绍一下什么是树状数组，它们的原理与结构是怎样，并通过实际题型来讲解。

线段树与树状数组的区别和特点：

它们的时间复杂度都是O(nlogn)

• 存储方式和空间复杂度不同。线段树使用树形结构存储，其空间复杂度通常较高；树状数组使用数组存储，空间复杂度较低。
• 操作复杂度不同。线段树和树状数组在操作复杂度上有所差异，线段树的查询和更新操作的时间复杂度通常为$O(logn)$或$O(lo{g}^{2}n)$，而树状数组的查询和更新操作的时间复杂度为$O(logn)$。
• 应用场景不同。线段树适用于区间修改、区间查询的场景；树状数组适用于单点修改、区间查询的场景。
• 功能不同。线段树可以维护区间信息，包括区间和、最大值、最小值等；树状数组主要维护前缀和，通过特定操作也可以实现区间查询，但功能上不如线段树强大。

   总体来说，线段树的构造更难一些，但是功能很强，树状数组的实现较简单，但功能较弱（线段树包含树状数组）

什么是树状数组？

   顾名思义就是一个结构为树形结构的数组，于二叉树的结构类似但又不同，它是在二叉树的结构上删除了一些中间节点，来看两幅图就明白了.

1. 这是二叉树的结构

2. 这是树状数组的结构

   不难发现，树状数组相比于二叉树删除了一些节点，但是为什么要删除呢？这就和树状数组的一些性质(lowbit)有关了，不懂没关系，继续往下看.

前置知识—lowbit(x)运算

如何计算一个非负整数n在二进制下的最低位1及其后面的0构成的数？
例如：$44=(101100{)}_2$ ,最低为1和后面的0构成的数是$(100{)}_2=4$
所以$lowbit(44)=lowbit((101100{)}_2)=(100{)}_2=4$ ,那么lowbit运算时怎么实现的呢？

44的二进制=(101100)，我们对44的二进制数取反+1，也即~44+1,得到-44

-44的二进制=(010100)，然后我们把44和-44的二进制进行按位与运算，也即按位&得到,二进制000100，也就是十进制的4

所以lowbit(x) = x&(-x)

树状数组结构分析

   上文提到树状数组主要解决两个问题，单点修改和区间查询。它和前缀和操作一样，但时间复杂度却相差甚大。前缀和总操作的时间复杂度是$O(n)$而树状数组的时间复杂度是$O(logn)$。

   如图所示，树状数组中所有的奇数位都存的是自己本身（奇数位的二进制最后都是没有0，表示第0层），而对于偶数位，偶数位的二进制表示中末尾有几个0，就表示第几层。（以图中2，4，8 为例，2的二进制末尾有一个0，所以放在第一层，存放的内容是A[1]与A[2]的和。4放在第2层，存放前4个数的和）

   上面时树状数组的结构图，C[x]保存以x为根的子数中叶子节点值的和,原数组为A[]
那么原数组前4项的和C[4]=C[2]+C[3]+A[4]=C[1]+A[2]+C[3]+A[4]=A[1]+A[2]+A[3]+A[4],看似没有什么特点，别着急往下看

   我们通过观察节点的二进制数，进一步发现，树状数组中节点x的父节点为x+lowbit(x),例如C[2]的父节点为C[4]=C[2+lowbit(2)] (lowbit 函数：返回 x 的二进制表示中最低位的1对应的值)

单点修改，区间查询

   在进行单点修改的同时，需要更新其父节点，因为树状数组存的其实就是节点中所有子节点的和，例如我们对A[1]+k，那么祖先节点C[1],C[2],C[4],C[8]…都需要+k更新，此时我们就可以用lowbit操作实现.

# 定义 lowbit 函数：返回 x 的二进制表示中最低位的1对应的值
# 例如：lowbit(6)=2（6的二进制是 110，最低位的1对应 10）
def lowbit(x):
    return x & -x

# 定义树状数组的更新操作：在位置 x 增加 y
def add(x, y):
    # 从 x 开始，沿树状数组的父节点路径向上更新
    while x <= n:
        tree[x] += y
        x += lowbit(x)  # 移动到父节点

   那么单点修改实现了，如何实现区间查询呢？
   例如：我们需要查询前7项的区间和sum[7]

   通过图中不难看出，sum[7]=t[7]+t[6]+t[4] ,我们进一步发现,6=7-lowbit(7),4=6-lowbit(6)，所以我们可以通过不断的-lowbit操作来实现求和

# 定义树状数组的前缀和查询：返回 [1, x] 区间的和
def query(x):
    res = 0
    # 从 x 开始，沿树状数组的子节点路径向下累加
    while x > 0:
        res += tree[x]
        x -= lowbit(x)  # 移动到左兄弟节点
    return res

   这只能求区间$[1,x]$ 的区间和，那么如何求 $[L,R]$ 的区间和呢？，这时候利用前缀和相减的性质就可以了，$[L,R]=[1,R]-[1,L-1]$

   下面就是树状数组的经典模板题，大家一起来看一下吧。

题目： 动态求连续区间和

题目链接：1264. 动态求连续区间和

给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b]
的连续和。

输入格式
第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。
第二行包含 n 个整数，表示完整数列。
接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。数列从 1 开始计数。

输出格式
输出若干行数字，表示 k=0 时，对应的子数列 [a,b] 的连续和。

数据范围
$1\le n\le 100000$,
$1\le m\le 100000$，
$1\le a\le b\le n$,
数据保证在任何时候，数列中所有元素之和均在 int 范围内。

输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

输出样例：

11
30
35

思路

   本题就是树状数组的经典模板题，直接套用模板即可（上文中全部讲解过）。

代码及详细注释

# 读取输入：n 为数组长度，q 为操作次数
n, q = map(int, input().split())

# 数组初始化，索引从1开始（方便树状数组操作）
# num[0] 是占位符，实际数据从 num[1] 到 num[n]
num = [0] + list(map(int, input().split()))

# 树状数组初始化，大小为 n+1（索引从1到n）
tree = [0] * (n + 1)

# 定义 lowbit 函数：返回 x 的二进制表示中最低位的1对应的值
# 例如：lowbit(6)=2（6的二进制是 110，最低位的1对应 10）
def lowbit(x):
    return x & -x

# 定义树状数组的更新操作：在位置 x 增加 y
def add(x, y):
    # 从 x 开始，沿树状数组的父节点路径向上更新
    while x <= n:
        tree[x] += y
        x += lowbit(x)  # 移动到父节点

# 定义树状数组的前缀和查询：返回 [1, x] 区间的和
def query(x):
    res = 0
    # 从 x 开始，沿树状数组的子节点路径向下累加
    while x > 0:
        res += tree[x]
        x -= lowbit(x)  # 移动到左兄弟节点
    return res

# 初始化树状数组：将初始数据填充到树中
for i in range(1, n + 1):
    add(i, num[i])  # 将 num[i] 添加到位置 i

# 处理 q 次操作
while q:
    q -= 1
    # 读取操作类型和参数
    # k=0 表示区间查询 [a, b] 的和
    # k=1 表示在位置 a 增加 b
    k, a, b = map(int, input().split())
    
    if k == 0:
        # 计算区间和：sum([a, b]) = sum([1, b]) - sum([1, a-1])
        print(query(b) - query(a - 1))
    else:
        add(a, b)