线段树的单点与区间修改
极难2从改成绩到加分数：线段树的单点修改与朴素区间修改
你有没有遇到过这样的情况？老师拿着一张全班成绩单，想快速知道学号3到学号6的总分。如果每次都用计算器加一遍，人多了就累。更麻烦的是，如果小明把成绩从5分改成了6分，或者老师给学号2到6的同学每人加2分，所有统计结果都得跟着变。有没有一种数据结构，既能快速查询区间和，又能方便地修改单个或一片数据？这就是线段树的用武之地。
线段树（Segment Tree）是一种二叉树，它的每个节点代表数组的一个区间，节点里保存这个区间的某种统计信息（比如和、最大值、最小值）。它能在 O(log n) 时间内完成单点修改和区间查询，也能在 O(log n) 时间内完成区间修改（需要配合懒标记）。不过这节课我们先学习最简单的单点修改，以及为什么朴素区间修改会慢到让人抓狂。
1. 单点修改：只改一个人，更新所有“包含他”的小组
① 什么叫单点修改？
单点修改就是只改变数组中一个位置的值。比如全班有8个人，学号1~8，成绩分别是1,3,5,7,9,11,13,15。现在小明（学号4）把成绩从7分改成了100分。那么学号4所在的每一个区间（比如[1,8]、[1,4]、[3,4]、[4,4]）的和都要重新算。线段树是怎么做的呢？
② 沿着一条路径往下走
线段树的根节点表示整个数组[1,8]，它知道总和是1+3+5+7+9+11+13+15=64。叶子节点[4,4]存的是小明原来的成绩7。当我们要把位置4改成100时，从根开始：
- 根节点的区间是[1,8]，包含位置4，所以需要更新。
- 计算中点mid = (1+8)/2 = 4，位置4 ≤ 4，所以向左孩子[1,4]走。
- 左孩子区间[1,4]也需要更新，继续向左：mid=(1+4)/2=2，位置4>2，向右孩子[3,4]。
- [3,4]的mid=(3+4)/2=3，位置4>3，向右孩子[4,4]。
- 到达叶子[4,4]，将tree[4]改为100。
然后回溯：从叶子回到父节点，每返回一个节点，都重新计算左右孩子的和，作为当前节点的和。比如[3,4]的新和 = 左子[3,3]的5 + 右子[4,4]的100 = 105。依次往上，直到根。
这个过程就像你在班级里，只改了小明一个人的成绩，然后所有“包含小明的小组”的组长都重新算了一遍总分。因为树的高度是 log n，所以需要更新的节点只有从根到叶子的那一串，大约 log n 个，所以时间复杂度是 O(log n)。
③ 生活中的例子：零花钱记账
假设你有10个存钱罐，每个罐子里有不同数量的零花钱。你想知道第3到第7个罐子的总钱数。线段树可以快速回答。如果有一天你往第5个罐子里又塞了20元（单点修改），那么所有包含第5个罐子的区间（比如[1,10]、[5,10]、[5,5]）的和都要更新。线段树只改一条路径，很快。
④ 常见错误
新手写单点修改时容易犯这些错误：
- 忘记递归出口：当
l == r时到达叶子，必须更新tree[p]，然后直接返回，否则会无限递归。 - 下标搞错：递归时左孩子是
p*2，右孩子是p*2+1，数组下标从1开始。如果从0开始，要注意偏移。 - 回溯时没合并：更新完左右子节点后，一定要重新计算
tree[p] = tree[p*2] + tree[p*2+1]（求和的情况）。如果漏掉，父节点的值就还是旧的。 - 更新了线段树但忘记更新原始数组：大多数情况下我们只关心线段树，但如果你之后还要用原始数组
a，最好也同步更新。不过示例代码里只更新了tree，查询也是用tree，所以没问题。
2. 朴素区间修改：一人一改，慢得像蜗牛
① 什么是区间修改？
区间修改是指把数组中一段连续的区间里的每个元素都改成同一个值，或者都加上同一个数。比如老师宣布“学号2到6每人加2分”。如果线段树只支持单点修改，我们怎么做？
最直接的办法：对于区间 [2,6] 里的每个位置（2,3,4,5,6），分别调用一次单点修改函数 update(2), update(3), ..., update(6)。每次单点修改都需要 O(log n) 时间，区间长度是 len，总时间就是 O(len × log n)。
② 为什么慢？
假设班级有10000人，老师要给前5000人每人加1分。如果每人一次单点修改，就是 5000 × log₂10000 ≈ 5000 × 14 ≈ 70000 次操作。这还算勉强能接受。但如果老师每天都要加，或者区间长度接近整个数组（比如给全班10000人每人加1分），那就是 10000 × 14 = 140000 次操作，效率很低。
更可怕的数据：如果数组长度是 10⁵，区间修改长度也是 10⁵，那么需要 10⁵ × log₂10⁵ ≈ 10⁵ × 17 = 1.7×10⁶ 次操作，在竞赛中可能会超时。而且如果有很多次这样的修改，程序会慢得无法忍受。
③ 生活中的例子：全班加零花钱
你有一个零食店，每个货架上有不同数量的零食（数组）。你想给第3到第6个货架每个货架都加5包薯片。如果每次只改一个货架，你要跑4趟；如果货架有100个，你就要跑98趟。这太蠢了！理想的做法是：你只用告诉管理员“第3到第6号货架每架加5包”，管理员自己记录一笔“懒账”，等有人问总库存时再真正计算。这就是懒标记的思路。
④ 朴素区间修改的代码（演示用，不推荐实际使用）
下面这段代码只是为了展示“循环调用单点修改”的做法，实际中绝不会这样用，因为它太慢了。
// 朴素区间修改：循环调用单点修改（非常慢！）
void range_update_slow(int p, int l, int r, int L, int R, int val) {
for (int i = L; i <= R; i++) {
update(p, l, r, i, val); // 每次 O(log n)
}
}
如果你在竞赛中这样写，多半会超时。所以我们需要更好的方法——懒标记，下篇文章会详细讲解。
3. 完整代码示例：单点修改 + 区间查询（C++ 和 Python）
① C++ 版本（带详细注释）
#include <iostream>
using namespace std;
const int MAXN = 10000; // 数组最大长度
int a[MAXN]; // 原始数组（从下标1开始存）
int tree[4 * MAXN]; // 线段树数组，大小一般是4倍
// 建树：递归构建线段树
void build(int p, int l, int r) {
if (l == r) { // 到达叶子节点
tree[p] = a[l]; // 叶子存的就是原始值
return;
}
int mid = (l + r) / 2; // 取中点
build(p * 2, l, mid); // 递归左孩子 [l, mid]
build(p * 2 + 1, mid + 1, r); // 递归右孩子 [mid+1, r]
tree[p] = tree[p * 2] + tree[p * 2 + 1]; // 合并左右子树的和
}
// 单点修改：将位置 pos 的值改为 val
void update(int p, int l, int r, int pos, int val) {
if (l == r) { // 找到叶子，直接修改
tree[p] = val; // 也可以同时修改 a[l] = val，但这里只更新树
return;
}
int mid = (l + r) / 2;
if (pos <= mid) // 如果目标位置在左半区间
update(p * 2, l, mid, pos, val);
else // 否则在右半区间
update(p * 2 + 1, mid + 1, r, pos, val);
tree[p] = tree[p * 2] + tree[p * 2 + 1]; // 回溯时重新计算和
}
// 查询区间 [L, R] 的和
int query(int p, int l, int r, int L, int R) {
if (L <= l && r <= R) // 当前节点区间完全在查询区间内
return tree[p]; // 直接返回
if (r < L || l > R) // 当前区间与查询区间没有交集
return 0; // 返回0（因为求和，0不影响）
int mid = (l + r) / 2;
// 否则递归左右孩子，并合并结果
return query(p * 2, l, mid, L, R) + query(p * 2 + 1, mid + 1, r, L, R);
}
int main() {
int n = 8;
// 初始化原始数组：学号1~8的成绩
for (int i = 1; i <= n; i++) a[i] = 2 * i - 1; // 1,3,5,7,9,11,13,15
build(1, 1, n); // 从根节点（编号1，区间[1,n]）开始建树
cout << "Before update: sum [3,6] = " << query(1, 1, n, 3, 6) << endl;
// 单点修改：将位置4（小明）的成绩改为100
update(1, 1, n, 4, 100);
cout << "After update: sum [3,6] = " << query(1, 1, n, 3, 6) << endl;
return 0;
}
输出：
Before update: sum [3,6] = 32 (5+7+9+11=32)
After update: sum [3,6] = 125 (5+100+9+11=125)
② Python 版本（带详细注释）
class SegmentTree:
def __init__(self, data):
# data 是从0开始的列表，例如 [1,3,5,7,9,11,13,15]
self.n = len(data)
# 为了方便，把原始数据变成下标从1开始，前面补一个0
self.a = [0] + data[:]
# 线段树数组，大小 4*(n+1) 就够了
self.tree = [0] * (4 * (self.n + 1))
def build(self, p, l, r):
"""递归建树，p是当前节点编号，l,r是区间左右端点（从1开始）"""
if l == r:
self.tree[p] = self.a[l] # 叶子存原始值
return
mid = (l + r) // 2
self.build(p * 2, l, mid) # 左孩子
self.build(p * 2 + 1, mid + 1, r) # 右孩子
self.tree[p] = self.tree[p * 2] + self.tree[p * 2 + 1]
def update(self, p, l, r, pos, val):
"""单点修改：将位置pos（1-based）的值改为val"""
if l == r:
self.tree[p] = val
return
mid = (l + r) // 2
if pos <= mid:
self.update(p * 2, l, mid, pos, val)
else:
self.update(p * 2 + 1, mid + 1, r, pos, val)
self.tree[p] = self.tree[p * 2] + self.tree[p * 2 + 1]
def query(self, p, l, r, L, R):
"""查询区间 [L,R] 的和，L,R都是1-based"""
if L <= l and r <= R:
return self.tree[p]
if r < L or l > R:
return 0
mid = (l + r) // 2
return self.query(p * 2, l, mid, L, R) + self.query(p * 2 + 1, mid + 1, r, L, R)
def point_update(self, pos, val):
"""对外封装：pos是1-based，直接调用内部update"""
self.update(1, 1, self.n, pos, val)
def range_query(self, L, R):
"""对外封装：查询区间和"""
return self.query(1, 1, self.n, L, R)
if __name__ == "__main__":
arr = [1, 3, 5, 7, 9, 11, 13, 15] # 8个学生的成绩
st = SegmentTree(arr)
st.build(1, 1, st.n) # 从根节点开始建树
print("Before: sum [3,6] =", st.range_query(3, 6)) # 应输出32
st.point_update(4, 100) # 学号4改为100
print("After: sum [3,6] =", st.range_query(3, 6)) # 应输出125
运行结果同上。
4. 区间修改的思考：为什么需要懒标记？
从上面可以看到，如果区间很长，用单点修改循环去做，时间会爆炸。比如班里1000人，老师要给第1~999人每人加10分。如果用单点修改，就要做999次更新，每次O(log n)≈10，总共近一万次操作，而实际只需要一次操作就能完成。
那有没有办法只改树上的几个节点，就能代表整个区间都加了分？比如老师加分的范围是[2,6]，我们能不能在树上找到一个“覆盖”这个区间的几个大区间节点，只改它们？例如[2,2]、[3,3]、[4,4]、[5,5]、[6,6]需要5个叶子，但我们可以用[2,2] + [3,6]两个节点？[3,6]是一个节点，但它的值是子节点的和，如果我们直接给[3,6]这个节点加上“每个元素加2”，那么它本身的和应该增加 2 × 区间长度 = 2×4=8。可是它的子节点并没有真的更新，如果以后有人要查询[3,4]这个子区间，就会出错，因为[3,4]没有收到“每个加2”的信息。
所以我们需要一种机制，让节点知道“我下面所有叶子都要加一个数”，但又不需要立刻往下传。等到真的要查询子区间时，再把“加的数”往下传递。这个机制就是懒标记（Lazy Tag）。懒标记就像一个“待办事项”，记录在这个节点上，等需要的时候再处理。这样就可以让区间修改也达到 O(log n) 的时间。
下篇文章我们就会学习如何用懒标记实现高效的区间修改。学完之后，你就可以轻松处理“全班加五分”这样的批量操作了。
5. 总结要点
| 操作 | 方法 | 时间复杂度 |
|---|---|---|
| 单点修改 | 从根到叶子递归更新，回溯合并 | O(log n) |
| 朴素区间修改 | 循环调用单点修改 | O(len × log n) |
| 懒标记区间修改 | 用标记延迟更新，下节课学习 | O(log n) |
- 单点修改就像只改一个人的成绩，只影响包含他的那条路径。
- 朴素区间修改要一个个改，太慢，所以需要懒标记。
- 写代码时注意递归出口、回溯合并、数组大小开4倍。
- 线段树不仅能求和，还能求最大值、最小值、位运算等等，只要满足“可以合并”的性质。
相关指引
如果你已经掌握了单点修改，那么下一步可以学习：
- [线段树的懒标记与区间修改]（即将推出）
- [线段树求区间最大值与最小值]
- [树状数组（另一种高效区间查询结构）]
- [分块算法（朴素的区间修改思路）]
继续加油，数据结构的世界很有趣！
例题精讲
线段树中，单点修改（更新一个位置的值）的时间复杂度是多少？
在线段树的区间修改中，如果使用懒标记（lazy tag），则每次修改操作的时间复杂度可以降低为O(log n)。
以下为线段树单点修改的代码片段（数组实现），请填空：
void update(int node, int l, int r, int idx, int val) {
if (l == r) {
tree[node] = val;
return;
}
int mid = (l + r) / 2;
if (idx <= mid) ___;
else update(node*2+1, mid+1, r, idx, val);
tree[node] = tree[node*2] + tree[node*2+1];
}线段树进行区间修改（如区间加一个值）后，若要进行区间查询（如区间和），在查询过程中，必须执行以下哪个操作？
在线段树中，单点修改可以看作是区间修改的一种特例（区间长度为1）。