核心逻辑与数学原理
线段树（Segment Tree）本质上是一种基于分治（Divide and Conquer）思想的二叉搜索树，用于维护区间信息。它将一个长度为 $N$ 的线性区间划分成若干个对数级别的子区间，每个节点代表一个闭区间 $[L, R]$。
空间拓扑结构
对于当前节点编号为 $u$，其左子节点编号为 $u \ll 1$（即 $2u$），右子节点编号为 $u \ll 1 | 1$（即 $2u + 1$）。 叶子节点满足 $L = R$，代表单点。非叶子节点的划分点为 $M = (L + R) \gg 1$，左子树维护 $[L, M]$，右子树维护 $[M + 1, R]$。
为了保证完全二叉树的索引不越界，数组空间必须严格开辟到 $4N$。
渐进复杂度证明
- 分治建树（Build）：递归触及所有叶子节点，节点总数为 $\sum_{i=0}^{\lceil \log_2 N \rceil} 2^i < 4N$，时间复杂度为 $O(N)$。
- 单点更新（Update）：从根节点直扑叶子节点，路径长度即为树高，时间复杂度为 $O(\log N)$。
- 区间二分求和（Query）：任何一个区间 $[l, r]$ 最多被拆分成 $2 \log N$ 个线段树上的完备子区间。证明：在树的每一层，最多有两个节点被部分覆盖并继续向下递归，其余节点要么完全包含，要么完全不包含。时间复杂度严格为 $O(\log N)$。
状态设计与算法推导
1. 分治建树
定义递归函数 build(u, l, r)。
若 $l = r$，说明到达叶子节点，直接读取原数组数据赋值：
$$tree[u] = a[l]$$
否则，令 $m = (l + r) \gg 1$，递归构建左右子树，最后执行 pushup(u)：
$$tree[u] = tree[u \ll 1] + tree[u \ll 1 | 1]$$
2. 单点更新
定义递归函数 update(u, l, r, pos, val)。
通过二分位置 pos 锁定分支。若 $pos \le m$，递归左子树；否则递归右子树。
触及叶子节点（即 $l = r = pos$）时执行修改：
$$tree[u] = val$$
回溯时，必须沿着更新路径逐层调用 pushup(u) 更新祖先节点的值。
3. 区间二分求和
定义递归函数 query(u, l, r, ql, qr)。
当前节点区间 $[l, r]$ 与查询区间 $[ql, qr]$ 存在三种关系：
- $[l, r] \subseteq [ql, qr]$：当前区间被完全包含，直接返回 $tree[u]$。
- $[l, r] \cap [ql, qr] = \emptyset$：当前区间与查询区间无交集，返回 $0$。
- 部分交集：令 $m = (l + r) \gg 1$。
若 $ql \le m$，累加左子树贡献：
query(u << 1, l, m, ql, qr)。 若 $qr > m$，累加右子树贡献：query(u << 1 | 1, m + 1, r, ql, qr)。
C++ 标准源码（NOIP风格）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 严格遵循 NOIP/Linux 环境规范，禁用万能头，大数据量下必须使用快读
inline long long read() {
long long x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
const int MAXN = 100005;
long long tree[MAXN << 2]; // 致命踩坑点：线段树数组大小必须开到原数组的 4 倍
long long a[MAXN];
inline void pushup(int u) {
tree[u] = tree[u << 1] + tree[u << 1 | 1];
}
void build(int u, int l, int r) {
if (l == r) {
tree[u] = a[l];
return;
}
int m = (l + r) >> 1;
build(u << 1, l, m);
build(u << 1 | 1, m + 1, r);
pushup(u);
}
void update(int u, int l, int r, int pos, long long val) {
if (l == r) {
tree[u] = val; // 找到目标单点，直接覆盖或累加
return;
}
int m = (l + r) >> 1;
if (pos <= m) {
update(u << 1, l, m, pos, val);
} else {
update(u << 1 | 1, m + 1, r, pos, val);
}
pushup(u); // 回溯时必须更新祖先节点，否则查询数据断层
}
long long query(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return tree[u]; // 当前区间被完全包含，直接返回
}
int m = (l + r) >> 1;
long long res = 0;
if (ql <= m) {
res += query(u << 1, l, m, ql, qr);
}
if (qr > m) {
res += query(u << 1 | 1, m + 1, r, ql, qr);
}
return res;
}
int main() {
// 优化标准流性能
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n = read();
int m = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
}
build(1, 1, n);
for (int i = 0; i < m; ++i) {
int opt = read();
if (opt == 1) {
int pos = read();
long long val = read();
update(1, 1, n, pos, val);
} else if (opt == 2) {
int ql = read();
int qr = read();
printf("%lld\n", query(1, 1, n, ql, qr));
}
}
return 0;
}
NOIP 实战避坑指南
1. 数组越界与物理空间不足
线段树是满二叉树的退化形式。在线性区间长度为 $N$ 时，最坏情况下末端叶子节点的下标会逼近 $4N$。
若仅开辟 $2N$ 或 $3N$ 空间，代码在处理 $N$ 为非 $2$ 的幂次且数据偏向右侧子树时，执行 u << 1 | 1 会直接触发 Segmentation Fault 或死锁。必须严格声明 `MAXN << 2。
2. 运算符优先级灾难
写线段树常使用位运算提升效率。
注意：+、- 的优先级高于 <<、>>。
错误示范：int m = l + r >> 1;（等价于 (l + r) >> 1，此行无误）。
错误示范：build(u << 1, l, m + 1); 中若误写为 u << 1 + 1，由于 + 优先，实际执行的是 u << (1 + 1) 即 u << 2。涉及位运算时，必须强制加括号，如 (u << 1) | 1。
3. 数据溢出
区间求和题目中，即使原数组都在 int 范围内，累加后的答案、单点修改的增量极易突破 $2^{31}-1$。线段树数组 tree[] 以及查询函数的返回值必须全部声明为 `long long`。
经典 NOIP/洛谷 真题
1. 洛谷 P1303 / 基础改编版：单点修改与区间查询基准
- 题意描述：给定一个长度为 $N$ 的序列，支持两种操作：修改某个位置的值；求区间 $[L, R]$ 的元素和。
- 问题本质：线段树经典模板。
- 核心解题思路：使用单点更新线段树。通过
build在 $O(N)$ 时间内建立拓扑结构，update每次耗费 $O(\log N)$ 维护单点及祖先链，query将目标区间切分为至多 $2\log N$ 个线段树节点，直接累加返回，完美替代低效的 $O(N)$ 暴力扫描。
2. 洛谷 P7075 [CSP-S 2020] 儒略日 / 树形数据检索化点
- 题意描述：给定多个询问，每个询问要求计算从公元前 4713 年 1 月 1 日开始经过 $Q$ 天后的具体日期。
- 问题本质：大模拟或非平凡二分。在线段树框架下，它可以抽象为在值域区间上寻找第一个满足前缀天数大于等于 $Q$ 的位置。
- 核心解题思路：利用基础线段树的区间二分求和逻辑。将各年份/月份拥有的天数作为基础数组建树，每个节点维护对应时间段的总天数。面对询问 $Q$，不需要在外部二分，直接在线段树上进行“树上二分”：若左子树总天数 $\ge Q$，则答案在左子树，直接进入左子树；否则 $Q$ 减去左子树天数，进入右子树。单次查询复杂度硬核压至 $O(\log N)$。