线段树学习笔记（c++）
一、什么是线段树？
线段树(Segment Tree)是一种的二叉树数据结构，基于分治思想，用于高效地处理区间操作。
二、线段树的优点
假设有一个数组 A，大小为 N。
| 操作类型 | 普通数组 | 前缀和数组 | 线段树 |
|---|---|---|---|
| 单点修改 | O(1) | O(N) (需重建) | |
| 区间查询 | O(N) | O(1) |
普通数组：修改快，但求区间和慢（要遍历）。
前缀和：查询快，但只要修改一个数，整个前缀和数组都要更新。
线段树：修改和查询都很快，是一种完美的平衡。
三、线段树的结构原理
线段树的核心思想是分治 。
线段树的每一个节点都代表一个区间。
假设我们的数组长度为 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(
)，引入 Lazy Tag 后，区间修改和区间查询的复杂度依旧能保持在O(
)。
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; }
