第二十八章：树状数组与线段树——区间问题的两把利器
说实话，刚接触算法竞赛那会儿，我特别怕区间问题。给你一个数组，动不动就要查询某段的和，或者更新某个位置的值。暴力做吧，O(n) 的复杂度，数据量一大就崩。后来我学到了树状数组和线段树，才真正体会到什么叫「数据结构之美」。
这一章，我们就来聊聊这两个东西。它们都能处理区间问题，但各有各的脾气。我个人习惯是：能上树状数组就上树状数组，搞不定再请线段树出场。
一、树状数组：轻量级的区间武器
树状数组（Binary Indexed Tree，BIT）是个很有意思的结构。它用数组来模拟树形结构，核心思想是利用二进制拆分。
你想想看，一个整数可以拆成若干个 2 的幂次之和。比如 7 = 4 + 2 + 1。树状数组就是基于这个原理，把区间查询拆成若干个前缀的累加。
1.1 lowbit 函数——树状数组的灵魂
树状数组里有个核心操作叫 lowbit，它返回一个数二进制表示中最低位的 1 所对应的值。比如 lowbit(6) = 2，因为 6 的二进制是 110，最低位的 1 对应 2。
int lowbit(int x) {
return x & (-x);
}这个写法很巧妙。负数的补码表示是取反加一，x & (-x) 就能把最低位的 1 保留下来。我在项目中第一次看到这个写法时，愣了半天才想明白。
1.2 单点更新
更新操作很简单：从当前位置开始，不断加上 lowbit，更新所有受影响的节点。
void update(int i, int delta) {
while (i <= n) {
tree[i] += delta;
i += lowbit(i);
}
}比如更新位置 3，它会更新 tree[3]、tree[4]、tree[8]…… 为什么？因为树状数组里，每个节点管理的区间长度就是 lowbit(i)。
1.3 区间查询
查询前缀和是反向操作：从当前位置开始，不断减去 lowbit，累加沿途的值。
int query(int i) {
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= lowbit(i);
}
return sum;
}要查询 [l, r] 的区间和，就是 query(r) - query(l-1)。
核心要点：树状数组只能处理前缀可合并的问题，比如求和、求异或。对于区间最值，它处理起来比较麻烦，这时候就要请线段树出场了。
我的经验：树状数组的代码量很小，常数也小。我在做在线评测系统时，处理大量单点更新、区间求和请求，树状数组比线段树快 30% 左右。能用树状数组解决的问题，我绝不写线段树。
二、线段树：全能型区间选手
线段树就灵活多了。它把区间递归地分成两半，每个节点代表一个区间。建树、更新、查询都是 O(log n) 的复杂度。
我曾经在做一个股票交易系统时，需要同时维护区间和、区间最大值、区间最小值。树状数组搞不定，线段树一把梭全搞定。
2.1 建树
线段树通常用数组实现，根节点是 1，左孩子是 2*i，右孩子是 2*i+1。建树的过程就是递归地构建每个节点。
void build(int node, int l, int r) {
if (l == r) {
tree[node] = arr[l];
return;
}
int mid = (l + r) >> 1;
build(node*2, l, mid);
build(node*2+1, mid+1, r);
tree[node] = tree[node*2] + tree[node*2+1];
}嗯，这里要注意：如果维护的是最大值，那合并操作就是取 max。不同的需求对应不同的合并逻辑。
2.2 单点更新
更新操作也是递归的。找到叶子节点，更新它，然后回溯更新父节点。
void update(int node, int l, int r, int pos, int val) {
if (l == r) {
tree[node] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
update(node*2, l, mid, pos, val);
else
update(node*2+1, mid+1, r, pos, val);
tree[node] = tree[node*2] + tree[node*2+1];
}2.3 区间查询
查询时，如果当前节点区间完全在查询范围内，直接返回；否则递归查询左右子树。
int query(int node, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr)
return tree[node];
int mid = (l + r) >> 1;
int res = 0;
if (ql <= mid)
res += query(node*2, l, mid, ql, qr);
if (qr > mid)
res += query(node*2+1, mid+1, r, ql, qr);
return res;
}避坑指南：我曾经在写线段树时，忘记处理区间完全包含的情况，结果递归到叶子节点才返回，直接超时。记住：能提前返回就提前返回，这是线段树性能的关键。
三、区间最值问题
区间最值（RMQ，Range Minimum/Maximum Query）是线段树的经典应用。你只需要把建树和查询中的「求和」改成「取 max」或「取 min」就行。
树状数组也能做 RMQ，但只支持前缀最值，不支持任意区间。而且更新操作比较麻烦。所以，遇到区间最值问题，我一般直接上线段树。
// 建树时维护最大值
tree[node] = max(tree[node*2], tree[node*2+1]);
// 查询时取最大值
int res = -INF;
if (ql <= mid)
res = max(res, query(node*2, l, mid, ql, qr));
if (qr > mid)
res = max(res, query(node*2+1, mid+1, r, ql, qr));性能对比：
| 操作 | 树状数组 | 线段树 |
|---|---|---|
| 单点更新 | O(log n) | O(log n) |
| 区间求和 | O(log n) | O(log n) |
| 区间最值 | 不支持 | O(log n) |
| 代码量 | 小 | 中等 |
| 常数 | 小 | 较大 |
四、知识体系总览
下面这张图是我自己整理的，把树状数组和线段树的核心知识点串了起来。你看一眼就能明白它们各自擅长什么。
说白了，树状数组是「专才」，线段树是「通才」。专才效率高，通才更灵活。你根据实际需求选就行。
我的建议：初学者先掌握树状数组，代码短，容易调试。等树状数组用熟了，再学线段树。我当年就是这么过来的，一步一个脚印，稳得很。
好了，这一章的内容就到这里。记住：数据结构是工具，不是目的。理解它们的原理，知道什么时候用哪个，比死记硬背代码重要得多。
公众号:蓝海资料掘金营，微信deep3321