线段树是一种高效处理区间查询与更新的数据结构，通过数组模拟二叉树实现，支持区间和、最值等操作。其核心包括构建（build）、查询（query）和更新（update）三个函数，并利用懒惰标记（lazy propagation）优化区间修改，避免重复计算。树的每个节点代表原数组的一个区间，根节点覆盖整个区间，叶子节点对应单个元素。通常将线段树数组大小设为原数组长度的4倍以保证空间充足。构建过程递归分割区间并合并子节点值；查询时若当前节点完全包含于目标区间则直接返回值，否则下放懒惰标记后递归查询左右子树；更新时先下放标记，若当前区间完全被覆盖则打上懒惰标记并立即应用，否则继续递归更新子区间并回传结果。该结构适用于频繁进行区间操作的场景，具有较高的时间效率和实用性。
线段树是一种高效处理区间查询和区间更新的数据结构，特别适用于频繁进行区间操作的场景，比如求区间和、区间最小值/最大值，以及支持单点或区间修改。在C++中实现一个支持区间查询与懒惰更新（lazy propagation）的线段树并不复杂，下面是一个完整且实用的实现。
线段树基本结构设计
线段树本质上是一棵二叉树，通常用数组模拟。每个节点代表原数组的一个区间，根节点代表整个区间 [0, n-1]，叶子节点代表单个元素。
为了方便实现，我们使用以下成员：
- tree[]：存储线段树节点的值（如区间和）
- lazy[]：懒惰标记数组，用于延迟更新
- n：原始数组长度
线段树数组大小一般开到 4 倍原数组长度，以保证空间充足。
立即学习“C++免费学习笔记（深入）”；
构建线段树（build）
从底向上构造线段树，递归地将区间一分为二，直到单个元素为止。
void build(vector& arr, int node, int start, int end) { if (start == end) { tree[node] = arr[start]; } else { int mid = (start + end) / 2; build(arr, 2*node, start, mid); build(arr, 2*node+1, mid+1, end); tree[node] = tree[2*node] + tree[2*node+1]; // 区间和 } }
区间查询（query）
查询 [l, r] 范围内的和，过程中需要处理懒惰标记。
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0; // 无交集
if (l <= start && end <= r) return tree[node]; // 完全包含
int mid = (start + end) / 2;
push(node, start, end); // 下放懒惰标记
int left_sum = query(2*node, start, mid, l, r);
int right_sum = query(2*node+1, mid+1, end, l, r);
return left_sum + right_sum;
}
区间更新（update）与懒惰传播（push）
对区间 [l, r] 增加一个值 val，使用懒惰标记避免重复计算。
void push(int node, int start, int end) {
if (lazy[node]) {
tree[node] += (end - start + 1) * lazy[node];
if (start != end) { // 非叶子，传递标记
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
}
void update(int node, int start, int end, int l, int r, int val) {
push(node, start, end); // 先下放标记
if (r < start || end < l) return;
if (l <= start && end <= r) {
lazy[node] += val;
push(node, start, end); // 立即应用
return;
}
int mid = (start + end) / 2;
update(2*node, start, mid, l, r, val);
update(2*node+1, mid+1, end, l, r, val);
tree[node] = tree[2*node] + tree[2*node+1];
}
基本上就这些。初始化时调用 build，查询调用 query，更新调用 update，注意每次操作都处理 lazy 标记。这种实现方式简洁高效，适合大多数区间问题。
