线段树与树状数组：区间查询、单点更新
说到区间查询和单点更新，这俩数据结构我用了快十年了。说实话，刚入行那会儿我总觉得线段树太复杂，动不动就写崩。后来带团队做性能优化，才发现这玩意儿是真香——尤其是处理那种「数组可修改，还要频繁查区间和」的场景。
今天咱们就把线段树和树状数组掰开揉碎了讲清楚。你想想看，一个数组，动不动要改某个位置的值，还要快速知道某段区间的和，暴力法肯定不行。那怎么办？
核心问题：区域和检索 - 数组可修改
先看一道经典题：LeetCode 307. 区域和检索 - 数组可修改。题目很简单：
- 给你一个数组
nums - 支持两种操作：更新某个下标的值，查询某个区间的和
- 要求两种操作都高效
暴力法更新是 O(1)，但查询是 O(n)。前缀和查询是 O(1)，但更新是 O(n)。都不行。我们需要一种「平衡」的数据结构——更新和查询都在 O(log n) 级别。
嗯，这就是线段树和树状数组的用武之地。
线段树：分治思想的极致体现
我个人习惯把线段树理解成「一棵二叉树，每个节点代表一个区间」。根节点是整个数组，叶子节点是单个元素，内部节点是左右子区间的合并结果。
说白了，就是递归地把大问题拆成小问题，然后合并答案。
线段树的核心操作
- 建树：递归构建，每个节点存区间和
- 更新：从根到叶子，更新路径上的所有节点
- 查询：递归查找，如果当前区间完全在查询范围内，直接返回；否则继续往下找
关键点：线段树的数组大小一般是 4n，这是经验值。为什么是 4n？因为最坏情况下树的高度是 log₂n，节点数不超过 4n。我刚开始写的时候总用 2n，结果经常越界……后来就老老实实开 4n 了。
代码实现（C++）
class SegmentTree {
private:
vector<int> tree;
int n;
void build(const vector<int>& nums, int node, int l, int r) {
if (l == r) {
tree[node] = nums[l];
return;
}
int mid = l + (r - l) / 2;
build(nums, node * 2, l, mid);
build(nums, node * 2 + 1, mid + 1, r);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void update(int node, int l, int r, int idx, int val) {
if (l == r) {
tree[node] = val;
return;
}
int mid = l + (r - l) / 2;
if (idx <= mid) update(node * 2, l, mid, idx, val);
else update(node * 2 + 1, mid + 1, r, idx, val);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int query(int node, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[node];
int mid = l + (r - l) / 2;
int sum = 0;
if (ql <= mid) sum += query(node * 2, l, mid, ql, qr);
if (qr > mid) sum += query(node * 2 + 1, mid + 1, r, ql, qr);
return sum;
}
public:
SegmentTree(const vector<int>& nums) {
n = nums.size();
tree.resize(4 * n);
build(nums, 1, 0, n - 1);
}
void update(int idx, int val) {
update(1, 0, n - 1, idx, val);
}
int sumRange(int l, int r) {
return query(1, 0, n - 1, l, r);
}
};小技巧：我习惯用 node * 2 和 node * 2 + 1 表示左右孩子，这样比用结构体指针快得多。面试时也推荐这么写，简洁明了。
树状数组：更轻量的选择
树状数组（Fenwick Tree）是线段树的「轻量版」。它只能处理前缀和相关的操作，但代码量少、常数小、跑得快。
我记得有一次做实时数据统计，要求 QPS 上万，线段树扛不住，换成树状数组直接起飞。嗯，这就是它的优势。
核心思想
树状数组利用的是「二进制拆分」。每个下标 i 维护的是区间 [i - lowbit(i) + 1, i] 的和。其中 lowbit(i) = i & (-i)，表示 i 的二进制中最低位的 1 所代表的值。
你想想看，更新时只需要沿着 i += lowbit(i) 往上走，查询时沿着 i -= lowbit(i) 往下走，都是 O(log n)。
代码实现（C++）
class FenwickTree {
private:
vector<int> bit;
int n;
public:
FenwickTree(int size) : n(size), bit(size + 1, 0) {}
void update(int idx, int delta) {
while (idx <= n) {
bit[idx] += delta;
idx += idx & -idx;
}
}
int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= idx & -idx;
}
return sum;
}
int rangeSum(int l, int r) {
return query(r) - query(l - 1);
}
};注意：树状数组的下标从 1 开始。我曾经在项目里直接用原数组下标 0，结果查了半天 bug……后来统一改成 1-based，世界清净了。
线段树 vs 树状数组：怎么选？
| 特性 | 线段树 | 树状数组 |
|---|---|---|
| 代码量 | 较大（约 40-60 行） | 较小（约 15-20 行） |
| 常数 | 较大 | 较小 |
| 支持的操作 | 区间和、区间最值、区间更新等 | 前缀和、区间和（需差分） |
| 适用场景 | 复杂区间操作 | 简单区间求和 |
我的建议是：如果只是求区间和、单点更新，优先用树状数组。如果涉及区间最值、区间更新、或者需要更灵活的操作，那就上线段树。
知识体系图
下面这张图帮你理清本章的核心逻辑：
避坑指南
我曾经在项目里用线段树处理一个百万级数据的区间更新，结果递归太深导致栈溢出。后来改成迭代式线段树才解决。所以给你几个建议：
- 递归深度问题：数据量超过 10⁵ 时，考虑用迭代式线段树或树状数组
- 下标越界：线段树数组开 4n，树状数组开 n+1，别省这点空间
- 更新 vs 查询：树状数组的更新是加一个 delta，不是直接赋值。如果要赋值，需要先算出差值
- 区间查询的边界：注意闭区间还是开区间，我习惯用闭区间 [l, r]
面试小技巧：面试官让你写线段树时，可以先问清楚数据范围和操作类型。如果只是区间求和，直接上树状数组，面试官会觉得你「懂取舍」。
总结
线段树和树状数组，说白了就是「用空间换时间」的典型代表。它们把 O(n) 的查询或更新降到了 O(log n)，代价是多花一点内存。
我个人更推荐先掌握树状数组，因为它简单、高效、不容易写错。等遇到更复杂的场景（比如区间最值、区间更新），再上线段树也不迟。
嗯，今天就到这里。代码多敲几遍，自然就熟了。