线段树——分而治之的区间管理高手
较难4线段树——分而治之的区间管理高手
它是什么？用来干什么？
你有没有遇到过这样的问题：老师手里有一张全班同学的数学成绩单，你不仅想知道某几个连续同学的总分（比如第2名到第5名的总分），还要随时修改某个同学的成绩（比如把第3名的分数改成95分）。如果每次都要重新累加，效率太低了。
线段树就是解决这类问题的利器。它是一棵二叉树，把一个大区间（比如全班1~40号同学）不断对半切开，分成越来越小的区间，直到每个区间只剩一个元素（单个同学）。这样，每个区间都有“负责人”记录这段区间上我们关心的信息——比如总和、最大值、最小值、乘积等。不管是查询任意一段区间，还是修改某个位置的值，都只需要沿着树走几条路，时间非常快，只有 O(log n)（n是总人数）。
打个比方：线段树就像一本层层划分的“责任分区册”。学校把整个年级分成两个“大组”，每个大组又分成两个“小组”……最后每个小组只有一个人。每个组长都记住自己小组的总分。你要知道某几个同学的总分，只需要找到覆盖他们的几个组长，把他们的成绩加起来就行，不用去问每一个同学。
线段树的样子
线段树每个节点代表一个区间 [l, r]，其中 l 是左端点，r 是右端点。它的左孩子负责左半边 [l, mid]，右孩子负责右半边 [mid+1, r]，这里 mid = (l + r) / 2（整数除法，向下取整）。叶子节点代表区间长度为1，也就是单个元素。
比如一个数组有5个元素（位置1~5），线段树长这样（括号里是区间范围，方括号里是存储的区间和）：
[1,5] 和=15
/ \
[1,3] 和=6 [4,5] 和=9
/ \ / \
[1,2]和=3 [3,3]=3 [4,4]=4 [5,5]=5
/ \
[1,1]=1 [2,2]=2
（这里元素值假设为1,2,3,4,5）
每个节点存储的信息可以根据需求选择：求区间和就存和，求最大值就存最大值，求最小值就存最小值。
动手做：建树（Build）
建树就是把原始数组的值“填”到线段树的叶子节点，然后递归向上计算父节点的值。
举个例子：你有一箱零食，你按照位置编号放在架子上（位置1~8）。你想知道任意连续几个零食的总重量。建树过程就像你先把每个零食单独称重（叶子），然后相邻的两个零食放一起称出总重（父节点），再把两个父节点合起来称……直到得到整个架子的总重。
代码中的建树函数：
void build(int node, int l, int r) {
// node: 当前节点编号（1号是根）
// l, r: 当前节点代表的区间范围
if (l == r) { // 叶子节点：单个元素
tree[node] = arr[l]; // 直接把数组的值放进来
return;
}
int mid = (l + r) / 2; // 分成两半
build(node*2, l, mid); // 递归建立左孩子
build(node*2+1, mid+1, r); // 递归建立右孩子
tree[node] = tree[node*2] + tree[node*2+1]; // 父节点 = 左孩子 + 右孩子
}
注意：这里 arr 是原始数组，我们通常从下标1开始存，方便处理区间。
修改一个值：点更新（Update）
假设你改变了某个位置上的零食重量，那么从叶子到根，所有包含这个位置的节点信息都要更新。就像你给某个同学重新称了体重，那么包含他的所有小组的总分都要重新计算。
更新步骤：
- 从根节点出发，看当前位置在左半边还是右半边。
- 一直往下走，直到走到叶子节点，把叶子节点的值改成新值。
- 返回的路上，重新计算每个父节点的值（左+右）。
void update(int node, int l, int r, int pos, int val) {
// pos: 要修改的位置
// val: 新的值
if (l == r) { // 找到了叶子节点
tree[node] = val;
return;
}
int mid = (l + r) / 2;
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]; // 重新计算父节点
}
查询一段区间：区间查询（Query）
现在想知道从第 ql 个到第 qr 个同学的总分。递归地处理：
- 如果当前节点区间完全在查询区间内 (
ql <= l && r <= qr)，直接返回这个节点存好的值（因为这段我们已经提前算好了）。 - 否则，就递归到左右孩子，把两边返回的结果加起来。
注意：要小心处理边界。例如查询 [2,4]，当前节点是 [1,3] 不完全包含，但它的左孩子 [1,2] 和右孩子 [3,3] 可能部分包含。
int query(int node, int l, int r, int ql, int qr) {
// ql, qr: 查询区间的左右端点
if (ql <= l && r <= qr) { // 当前区间被完全覆盖
return tree[node];
}
int mid = (l + r) / 2;
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;
}
来模拟一下：查询 [2,4] 的和，假设数组是 [1,2,3,4,5]。
- 根节点 [1,5] 不完全包含，mid=3。左边含部分（2<=3），右边也含部分（4>3）。
- 递归左孩子 [1,3]，不完全包含，mid=2。左边 (2<=2) 进入 [1,2]，右边 (3>2) 进入 [3,3]。
- [1,2] 完全在 [2,4] 内吗？不， [1,2] 不是完全在 [2,4] 内（因为1不在查询里），继续分。 [1,2] 的mid=1，左边 [1,1] 不满足 (ql<=1? 2<=1 否)，右边 [2,2] 满足 (2<=2<=4)，返回tree[2]=2。
- [3,3] 完全在 [2,4] 内（因为 2<=3<=4），返回3。
- 右孩子 [4,5]，mid=4，左边 [4,4] 完全包含返回4，右边 [5,5] 不包含（5>4）不进入。总和 2+3+4=9。
时间复杂度
- 建树：每个节点访问一次，节点数约 2n，所以 O(n)。
- 每次更新或查询：沿着树走一条路径，深度约 log₂n，所有 O(log n)。
当 n=100000 时，log₂n ≈ 17，非常快。
完整示例：班级成绩统计
下面是一个完整的程序，可以手动输入数组、查询区间和、修改某个位置的值。代码中加了中文注释，方便理解。
#include <iostream>
using namespace std;
const int N = 100005; // 数组最大长度
int tree[4 * N]; // 线段树数组，一般开4倍大小
int arr[N]; // 原始数组（下标从1开始）
// 建树：节点编号 node，管辖范围 [l, r]
void build(int node, int l, int r) {
if (l == r) {
tree[node] = arr[l];
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
// 点更新：把位置 pos 的值改为 val
void update(int node, int l, int r, int pos, int val) {
if (l == r) {
tree[node] = val;
return;
}
int mid = (l + r) / 2;
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];
}
// 区间查询：求 [ql, qr] 的和
int query(int node, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) { // 完全覆盖
return tree[node];
}
int mid = (l + r) / 2;
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;
}
int main() {
int n = 5; // 数组长度
// 原始数据：位置1到5 分别是 1,2,3,4,5
int init[] = {0, 1, 2, 3, 4, 5}; // 第0个不用
for (int i = 1; i <= n; i++) {
arr[i] = init[i];
}
build(1, 1, n); // 从根节点1开始建树
cout << "区间[2,4]的和：" << query(1, 1, n, 2, 4) << endl; // 输出 9
update(1, 1, n, 3, 10); // 把第3个元素改为10
cout << "修改后区间[2,4]的和：" << query(1, 1, n, 2, 4) << endl; // 输出 16
return 0;
}
常见错误（新手容易踩的坑）
-
数组大小开不够：线段树需要
4 * N的空间，因为一棵树节点数最多约4n。如果只开2*N或N，会导致数组越界，程序崩溃。记住：保险写法tree[4*N]。 -
忘记更新父节点：在
update函数里，修改完叶子节点后，一定要在返回前重新计算tree[node] = tree[node*2] + tree[node*2+1]。如果忘记，父节点信息就会错误。 -
查询时区间判断写反：常见错误是
if (ql <= l && r <= qr)写成了if (l <= ql && qr <= r)或者不等号方向反了。一定要记住：当前节点区间完全在查询区间内才直接返回，即查询区间[ql, qr]包含了当前区间[l, r]。 -
递归边界搞错：建树和查询时，
if (l == r)是叶子节点。但注意，当区间长度为1时，左右孩子递归会越界，所以要提前返回。 -
下标从0还是从1：为了方便，一般建议数组下标从1开始，这样区间
[l, r]里的 mid 计算(l+r)/2自然向下取整，不会有负数问题。如果从0开始，要小心处理边界。 -
忘记用
return或res累加：在query函数里，两个if只是判断是否要递归，最终要返回res。有人会忘记加最后的return res;。 -
大型递归导致栈溢出：C++ 递归深度通常有限制，但线段树深度只有
log₂n，n=10^5 时深度约17，没问题。但如果n很大（比如10^7）且递归实现，可能溢出，那时需要考虑非递归写法。
相关指引
学完线段树，你还可以继续探索：
- 树状数组：线段树的轻量级亲戚，只能处理前缀和和单点更新，但代码更短、常数更小。
- ST 表：专门用于静态区间最值查询（不能修改），预处理 O(n log n)，查询 O(1)，适合只查不更新的场景。
- 懒标记线段树：支持区间更新（比如把整个区间的每个数都加上一个值），需要引入“懒标记”延迟更新，是线段树的进阶用法，也是 CSP-S 的常考点。
- 动态开点线段树：当值域很大（比如 10^9）时，不能一次性分配4倍空间，可以用动态开点，只在需要时创建节点。
- 可持久化线段树：能查询历史版本，比如让你回答“第 k 次修改后，区间和是多少”。
线段树是处理区间问题的万能工具，掌握它之后，许多看似复杂的区间操作都能用递归分解解决，就像把一个复杂任务层层分包给小组长一样清晰。多加练习，就能熟练运用了！
例题精讲
线段树通常使用数组实现，对于一个长度为 n 的序列，线段树数组的大小通常开为 4n。以下关于这一做法的解释中最合理的是？
线段树不支持区间修改（如将区间内所有元素加上同一个值）和区间查询，只能完成单点修改和区间查询操作。
使用线段树求解静态数组的区间最大值（RMQ）问题时，预处理（建树）的时间复杂度是 O(n log n)。
以下是一个线段树实现区间求和与单点更新的模板，补全 update 函数（将位置 pos 的值增加 val）。
#include <iostream>
using namespace std;
const int MAXN = 100005;
int tree[4 * MAXN];
void build(int node, int l, int r) {
if (l == r) { cin >> tree[node]; return; }
int mid = (l + r) / 2;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void update(int node, int l, int r, int pos, int val) {
if (l == r) {
___;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) ___(1)___;
else ___(2)___;
___(3)___;
}给定一个长度为 10^5 的整数数组，需要支持 10^5 次操作，每次操作为「将区间 [l, r] 内的所有数开平方（下取整）」或「查询区间 [l, r] 的和」。采用线段树+懒标记实现时，以下哪种优化技巧可以保证时间复杂度？