树状数组只擅长"和"这类可以拆分再合并的信息——线段树用一棵真正的二叉树，能维护区间最大值、最小值等更丰富的统计量。
16.2 节的树状数组能高效维护"区间和"，靠的是Query(r) - Query(l-1)这个前缀相减的技巧——但这个技巧只对"和"这类可以做减法还原的信息有效。如果要维护的是区间最大值，"前 r 个数的最大值"减去"前 l-1 个数的最大值"根本得不出"[l,r] 区间的最大值"——最大值没有"减法逆运算"这回事。树状数组这时候就不够用了。
线段树（Segment Tree）用一棵更通用的二叉树结构，不管是区间和、区间最大值、区间最小值，只要"父节点的信息可以由左右孩子的信息合并得到"，都可以用线段树维护。
线段树是一棵二叉树：根节点管辖整个区间 [1,n]；每个节点如果管辖的区间长度大于 1，就从中点 mid 一分为二，左孩子管辖 [l, mid]，右孩子管辖 [mid+1, r]；管辖区间长度为 1 的节点是叶子节点，直接对应原数组的一个元素。每个节点存储它所管辖区间的统计信息（比如区间和），这个信息等于它左右孩子信息的合并（比如相加）。
还是 16.2 节的数组 a = [3, 2, 5, 6, 1, 4, 7, 2]（n=8），以维护"区间和"为例，画出完整的线段树：
log₂8=3 层再加叶子层，共 4 层。每个节点的值都等于它两个孩子值相加：[1,4]=16 正是 [1,2]=5 和 [3,4]=11 相加；根节点 [1,8]=30 正是整个数组的总和，和 16.2 节算出的 tree[8]=30 完全一致。建树是一个递归过程：如果 l==r（区间只剩一个元素），这是叶子节点，直接赋值为 a[l]；否则取中点 mid=(l+r)/2，递归建好左右两半，再把当前节点的值设为左右孩子值的合并。
查询区间 [ql, qr] 的和时，从根节点开始递归，每个节点管辖的区间 [l,r] 和查询区间 [ql,qr] 之间，只会是以下三种关系之一：
| 关系 | 怎么处理 |
|---|---|
| [l,r] 完全在 [ql,qr] 之外 | 和答案完全无关，直接返回 0（不再往下递归） |
| [l,r] 完全被 [ql,qr] 包含 | 这个节点存的值就是答案的一部分，直接返回该节点的值（不用再往下拆） |
| [l,r] 和 [ql,qr] 部分重叠 | 拆成左右两个孩子分别递归查询，把两边的结果加起来 |
用 Query(3, 6)（查询 a[3]+a[4]+a[5]+a[6]）具体走一遍：
| 当前节点 | 和 [3,6] 的关系 | 处理 |
|---|---|---|
| [1,8] | 部分重叠 | 拆成 [1,4] 和 [5,8]，分别递归 |
| ├─ [1,4] | 部分重叠（重叠部分是 [3,4]） | 拆成 [1,2] 和 [3,4] |
| │ ├─ [1,2] | 完全在 [3,6] 之外（2<3） | 直接返回 0 |
| │ └─ [3,4] | 完全被 [3,6] 包含 | 直接返回该节点的值 11 |
| ├─ [5,8] | 部分重叠（重叠部分是 [5,6]） | 拆成 [5,6] 和 [7,8] |
| │ ├─ [5,6] | 完全被 [3,6] 包含 | 直接返回该节点的值 5 |
| │ └─ [7,8] | 完全在 [3,6] 之外（7>6） | 直接返回 0 |
0 + 11 + 5 + 0 = 16，和直接计算 a[3]+a[4]+a[5]+a[6] = 5+6+1+4 = 16 一致。整个过程只碰到了 [1,2]、[3,4]、[5,6]、[7,8] 这几个节点，没有拆到叶子节点这么细——一旦某个节点的区间被查询区间"完整包含"，就不用再往下拆了，这正是线段树查询效率的关键。| 1 | int a[MAXN], tree[MAXN * 4]; // tree 数组大小要开到 4 倍，见 ⑦ 陷阱 |
| 2 | |
| 3 | void Build(int node, int l, int r) |
| 4 | { |
| 5 | if (l == r) { tree[node] = a[l]; return; } // 叶子节点，直接对应原数组 |
| 6 | int mid = (l + r) / 2; |
| 7 | Build(node * 2, l, mid); // 左孩子管辖 [l, mid] |
| 8 | Build(node * 2 + 1, mid + 1, r); // 右孩子管辖 [mid+1, r] |
| 9 | tree[node] = tree[node * 2] + tree[node * 2 + 1]; // ★ 合并：当前节点 = 左孩子 + 右孩子 |
| 10 | } |
| 11 | |
| 12 | // node 管辖 [l,r]；查询目标区间是 [ql,qr] |
| 13 | int Query(int node, int l, int r, int ql, int qr) |
| 14 | { |
| 15 | if (qr < l || r < ql) return 0; // 情况一：完全在外面 |
| 16 | if (ql <= l && r <= qr) return tree[node]; // 情况二：完全被包含 |
| 17 | int mid = (l + r) / 2; // 情况三：部分重叠，拆成两半 |
| 18 | return Query(node * 2, l, mid, ql, qr) |
| 19 | + Query(node * 2 + 1, mid + 1, r, ql, qr); |
| 20 | } |
| 21 | |
| 22 | void Update(int node, int l, int r, int pos, int val) // 把 a[pos] 改成 val |
| 23 | { |
| 24 | if (l == r) { tree[node] = val; return; } |
| 25 | int mid = (l + r) / 2; |
| 26 | if (pos <= mid) Update(node * 2, l, mid, pos, val); |
| 27 | else Update(node * 2 + 1, mid + 1, r, pos, val); |
| 28 | tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 修改后，沿途重新合并更新 |
| 29 | } |
tree[node*2] + tree[node*2+1] 换成 max(tree[node*2], tree[node*2+1])，第 15 行"完全在外面"的返回值从 0 换成一个足够小的数（比如 -INF，代表"不参与最大值比较"）——骨架完全不用变，这正是线段树比树状数组更通用的地方。tree 数组大小要开到原数组的 4 倍：线段树用 node*2、node*2+1 表示左右孩子（类似二叉堆的存储方式），当 n 不是 2 的整数次幂时，树不是"满二叉树"，实际用到的下标可能超过 2n，为了绝对安全，通常直接把 tree 数组开到 4×n，这是竞赛中约定俗成的写法，不需要精确计算最坏情况下到底需要多少。Update 递归返回后，必须重新合并当前节点的值——如果漏掉这一行，只有叶子节点被改了，它的祖先节点（比如根节点）仍然保留着修改前的旧值，后续查询会算出错误的结果。1~n；只需要维护区间和，优先选 16.2 的树状数组（代码短、常数小）；需要维护最大值、最小值等更复杂的信息，或者需要区间修改（把一整段都加上某个值）这类树状数组不擅长的操作，就用本节的线段树。三者结合，构成了竞赛中处理"带修改的区间信息维护"问题的核心工具箱。