一、什么是线段树？
线段树 (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, end) {
(start == end) {
tree[node] = arr[start];
;
}
mid = (start + end) / ;
left_node = node * ;
right_node = node * + ;
(left_node, start, mid);
(right_node, mid + , end);
(node);
}
