1. 题目背景与需求分析

这道题目来自信息学奥赛经典教材《信息学奥赛一本通》的P1535页，是一个典型的动态维护数列问题。题目要求我们处理一个包含最多10万个元素的数列，支持两种高频操作：单点修改和区间求和，总操作次数同样可能达到10万次。

1.1 核心需求拆解

我们需要设计一个数据结构，能够高效处理以下两种操作：

1. 单点修改（Update）：将数列中第a个元素增加b
2. 区间查询（Query）：查询数列中第a到第b个元素的连续和

1.2 性能要求分析

对于10^5级别的数据规模，任何单次操作复杂度为O(n)的算法都会在1秒的时限内超时。我们需要寻找一种能在O(logn)时间内同时兼顾"修改"与"查询"的数据结构。

2. 算法选型与比较

2.1 暴力数组法

最直观的解法是使用普通数组存储数据：

• 单点修改：O(1)
• 区间求和：O(n)

对于10^5次操作，最坏情况下时间复杂度为O(n^2)=10^10，显然会超时。

2.2 前缀和数组法

预处理出前缀和数组：

• 区间求和：O(1)
• 单点修改：O(n)

虽然查询变快了，但修改操作会退化为O(n)，同样无法满足要求。

2.3 线段树与树状数组

这两种数据结构都能在O(logn)时间内完成单点修改和区间查询：

• 线段树：功能更强大，但代码实现较复杂
• 树状数组：代码简洁，效率高，但功能相对有限

对于本题只需要单点修改和区间求和的需求，树状数组是最佳选择。

3. 树状数组原理详解

3.1 二进制索引思想

树状数组（Binary Indexed Tree，BIT）的核心思想是利用二进制索引来高效维护前缀和。它通过将前缀和分解为若干个"块"的组合，使得每次更新和查询都只需要访问O(logn)个块。

3.2 lowbit函数

树状数组的核心是lowbit函数：

int lowbit(int x) { return x & (-x); }

这个函数可以提取x的二进制表示中最低位的1及其后面的0所组成的数。例如：

• lowbit(6) = lowbit(110₂) = 10₂ = 2
• lowbit(8) = lowbit(1000₂) = 1000₂ = 8

3.3 树状数组结构

树状数组中的每个元素c[i]负责维护原数组中从i-lowbit(i)+1到i这个区间的和。这种结构形成了一个类似树形的层次关系：

• c[1] = a[1]
• c[2] = a[1]+a[2]
• c[3] = a[3]
• c[4] = a[1]+a[2]+a[3]+a[4]
• ...

4. 关键操作实现

4.1 单点更新（update）

当原数组第x个元素增加val时，我们需要更新所有包含该元素的c[i]：

void update(int x, ll val) { for(int i = x; i <= n; i += lowbit(i)) { c[i] += val; } }

更新过程是一个"向上爬"的过程，每次加上lowbit(i)就能找到下一个需要更新的节点。

4.2 前缀查询（sum）

查询前x个元素的和：

ll sum(int x) { ll ret = 0; while(x > 0) { ret += c[x]; x -= lowbit(x); } return ret; }

查询过程是一个"向左走"的过程，每次减去lowbit(x)就能找到下一个需要累加的块。

4.3 区间查询

利用前缀和的性质，区间[a,b]的和可以表示为sum(b)-sum(a-1)。

5. 完整代码解析

#include <iostream> using namespace std; typedef long long ll; int n, m; ll c[100010]; // 树状数组 int lowbit(int x) { return x & (-x); } void update(int x, ll val) { for(int i = x; i <= n; i += lowbit(i)) { c[i] += val; } } ll sum(int x) { ll ret = 0; while(x > 0) { ret += c[x]; x -= lowbit(x); } return ret; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++) { ll x; cin >> x; update(i, x); } while(m--) { int k, a; ll b; cin >> k >> a >> b; if(k == 0) { cout << sum(b) - sum(a - 1) << "\n"; } else { update(a, b); } } return 0; }

6. 性能分析与优化

6.1 时间复杂度

• 建树：O(nlogn)
• 每次操作：O(logn)
• 总时间复杂度：O((n+m)logn)

对于n,m=10^5的情况，总操作次数约为2×10^6，完全可以在1秒内完成。

6.2 空间复杂度

只需要一个长度为n+1的数组，空间复杂度为O(n)。

6.3 IO优化

对于高频IO操作，使用以下优化：

ios::sync_with_stdio(false); cin.tie(0);

这样可以解除cin与cout的绑定，显著提高IO速度。

7. 实战技巧与注意事项

7.1 数据类型选择

必须使用long long来存储数据和结果，因为：

• 单个元素可能很大（比如1e9）
• 多次累加后很容易超出int范围（2.1×10^9）

7.2 下标处理

树状数组的下标必须从1开始，因为：

• lowbit(0)=0会导致死循环
• 物理意义更明确（第1个元素、第2个元素...）

7.3 常见错误

1. 死循环：忘记检查x>0导致sum函数死循环
2. 溢出：使用int导致累加溢出
3. IO超时：使用endl而不是"\n"导致频繁刷新缓冲区
4. 下标混淆：将区间查询写成sum(b)-sum(a)（应该是sum(b)-sum(a-1)）

8. 树状数组的扩展应用

虽然本题只需要基本的单点修改和区间查询，但树状数组还可以支持：

8.1 区间修改+单点查询

通过差分数组的思想，可以实现：

• 区间修改：update(l, val), update(r+1, -val)
• 单点查询：sum(x)

8.2 区间修改+区间查询

需要维护两个树状数组，分别记录差分数组和i×差分数组，可以实现：

• 区间修改：类似上面的方法
• 区间查询：通过公式推导得到

8.3 二维树状数组

可以扩展到二维情况，支持二维平面上的单点修改和子矩阵求和。

9. 与其他数据结构的对比

9.1 与线段树的比较

9.2 适用场景选择

• 只需要前缀和/区间和：优先选择树状数组
• 需要复杂区间操作（如最值、区间修改等）：选择线段树
• 对代码简洁性要求高：树状数组
• 对功能扩展性要求高：线段树

10. 实际应用案例

树状数组在以下场景中非常有用：

1. 计算逆序对数
2. 维护动态排名
3. 处理平面扫描问题
4. 配合其他算法解决复杂统计问题

在算法竞赛中，树状数组因其高效和简洁，是解决动态统计问题的首选数据结构之一。掌握它的原理和实现，对于提高解题能力大有裨益。