一、什么是线段树？
线段树 (Segment Tree) 是一种二叉树数据结构，基于分治思想，用于高效地处理区间操作。
二、线段树的优点
假设有一个数组 A，大小为 N。
| 操作类型 | 普通数组 | 前缀和数组 | 线段树 |
|---|---|---|---|
| 单点修改 | O(1) | O(N) (需重建) | O(\log N) |
| 区间查询 | O(N) | O(1) | O(\log N) |
普通数组：修改快，但求区间和慢（要遍历）。 前缀和：查询快，但只要修改一个数，整个前缀和数组都要更新。 线段树：修改和查询都很快，是一种完美的平衡。
三、线段树的结构原理
线段树的核心思想是分治。 线段树的每一个节点都代表一个区间。
假设我们的数组长度为 4 [1, 2, 3, 4]： 根节点：存整个区间 [1, 4] 的和。 左子节点：存左半部分 [1, 2] 的和。 右子节点：存右半部分 [3, 4] 的和。 叶子节点：存单个元素的值（如 [1, 1], [2, 2] 等）。
任何一个大区间查询，都可以拆分成几个小区间节点的组合。 例如区间 [1, 3] 可由左子节点 [1, 2] 和叶子节点 [3, 3] 结合而成。
四、线段树的基本实现（基于 C++）
以下一个经典的线段树模板。因为其为完全二叉树，我们使用堆式存储（数组模拟树），通常数组大小开到 4N 以防止越界。
1. Push Up
Push Up 是维护线段树性质的关键。使用子节点的信息来更新父节点
const int N = 1000;
int tree[N * 4]; // 线段树数组
int arr[N]; // 原数组
// 如果是求和则 tree[node] = left + right；如果是求最大值则 tree[node] = max(left, right)。
void push_up(int node) {
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
2. 建树（Build）
node 当前线段树节点编号 (从 1 开始) start 当前节点代表区间的开始位置 end 当前节点代表区间的结束位置
void build(int node, int start, int end) {
// 递归出口：到达叶子节点
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = (start + end) / 2;
int left_node = node * 2;
int right_node = node * 2 + 1;
// 递归构建左右子树
build(left_node, start, mid);
build(right_node, mid + 1, end);
// 构建完子节点后，计算当前节点的值
push_up(node);
}
3. 单点更新（Update）
idx 要修改的原数组索引 val 要修改成的值
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
// 找到了叶子节点，修改它
arr[idx] = val;
tree[node] = val;
return;
}
int mid = (start + end) / 2;
int left_node = node * 2;
int right_node = node * 2 + 1;
// 判断 idx 在左边还是右边
if (idx <= mid) {
update(left_node, start, mid, idx, val);
} else {
update(right_node, mid + 1, end, idx, val);
}
// 修改完子节点后，记得更新父节点
push_up(node);
}
4. 区间查询（Query）
L 查询区间的左边界 R 查询区间的右边界 return 区间 [L, R] 的和
int query(int node, int start, int end, int L, int R) {
// 情况 1: 当前节点区间完全包含在查询区间内
// 如果当前节点区间被查询区间 [L, R] 完全覆盖，直接返回该节点存的值，不需要再往下找了
if (L <= start && end <= R) {
return tree[node];
}
int mid = (start + end) / 2;
int left_node = node * 2;
int right_node = node * 2 + 1;
int sum = 0;
// 情况 2: 查询区间有一部分在左子树
if (L <= mid) {
sum += query(left_node, start, mid, L, R);
}
// 情况 3: 查询区间有一部分在右子树
if (R > mid) {
sum += query(right_node, mid + 1, end, L, R);
}
return sum;
}
五、懒惰标记（Lazy Tag）
没有 Lazy Tag，线段树只能做'单点修改'。如果要做'区间修改'，普通方法需要一个个叶子节点去改，复杂度会退化成 O(N \log N)，引入 Lazy Tag 后，区间修改和区间查询的复杂度依旧能保持在 O(\log N)。
Lazy Tag 的本质是'不到万不得已，绝不干活'。当我们需要更新一个区间时，无需立即更新所有子节点，而是在当前节点打上标记，等到真正需要访问子节点时再下放标记。
1. Push Down
const int MAXN = 1000;
int tree[MAXN * 4];
int lazy[MAXN * 4]; // 增加一个 lazy[] 数组存放懒惰标记，和 tree[] 数组一一对应。
int arr[MAXN];
void push_down(int node, int start, int end) {
// 如果当前节点没有标记，就不用下放
if (lazy[node] == 0) return;
int mid = (start + end) / 2;
int left_node = node * 2;
int right_node = node * 2 + 1;
// 下放给左孩子
// 左孩子的值 = 原值 + (标记值 * 左孩子区间长度)
tree[left_node] += lazy[node] * (mid - start + 1);
lazy[left_node] += lazy[node]; // 标记叠加
// 下放给右孩子
tree[right_node] += lazy[node] * (end - mid);
lazy[right_node] += lazy[node]; // 标记叠加
// 以此节点的任务已完成，清零标记
lazy[node] = 0;
}
2. 区间修改 (Range Update)
void update_range(int node, int start, int end, int L, int R, int val) {
// 情况 1: 当前区间完全被包含在修改范围内
if (L <= start && end <= R) {
// 直接更新当前节点的值
tree[node] += val * (end - start + 1);
// 打上标记
lazy[node] += val;
return;
}
// 情况 2: 区间只有一部分重叠，必须往下走，先下放之前的标记
push_down(node, start, end);
int mid = (start + end) / 2;
if (L <= mid) update_range(node * 2, start, mid, L, R, val);
if (R > mid) update_range(node * 2 + 1, mid + 1, end, L, R, val);
// 子节点改完了，更新父节点
push_up(node);
}
3. 区间查询 (Range Query)
int query_range(int node, int start, int end, int L, int R) {
if (L <= start && end <= R) {
return tree[node];
}
// 在分裂查询之前，须先把当前节点的标记下放
push_down(node, start, end);
int mid = (start + end) / 2;
int sum = 0;
if (L <= mid) sum += query_range(node * 2, start, mid, L, R);
if (R > mid) sum += query_range(node * 2 + 1, mid + 1, end, L, R);
return sum;
}