线段树:单点修改与区间查询
代码模板线段树单点修改与区间查询的原理与实现(基础线段树)。
一句话算法
线段树把大区间不断分成左右两半,让一次修改或查询只访问和目标有关的
问题模型
给定长度为
- 单点修改:
a[x] += k。 - 区间查询:求
a[l] + ... + a[r]。
如果每次查询都扫描区间,最坏是
核心直觉
每个节点维护一个连续区间的答案。
例如维护区间和时:
sum([l,r]) = sum([l,mid]) + sum([mid+1,r])
这说明父节点的信息可以由两个孩子合并得到。
线段树适合维护满足“区间可合并”的信息,例如:
- 区间和;
- 区间最小值、最大值;
- 区间 gcd;
- 区间按位或、按位与。
为什么可以合并:结合律
“区间可合并”这句话的确切含义是:把两段的信息合成一段的那个运算,必须满足结合律。
设合并运算记作
意思是先合并哪一对不重要,括号加在哪里结果都一样。因此
注意它和另外两条常见性质互不蕴含:
| 性质 | 式子 | 和结合律的关系 |
|---|---|---|
| 结合律 | 本条 | |
| 交换律 | 另一件事,线段树不需要 | |
| 幂等律 | 又一件,线段树不需要 |
矩阵乘法是“有结合律但没有交换律”的典型例子,可见两者完全独立。
结合律解决了什么
线段树本质上做两件事:
- 把
递归切成左右两半,直到单点; - 回溯时用合并运算把两个儿子的信息合成父亲。
所以一次查询的实质是:把
| 问题 | 结合律怎么解决 |
|---|---|
| 建树时父亲信息由儿子合并而来,那查询时重新合并出来的结果,会等于原始区间真实的答案吗? | 会。建树和查询用的是同一批叶子、同一个顺序,只是括号不同,而结合律说明括号无关 |
| 线段树结构是固定的,但查询区间是任意的,切出来的段数和形状每次都不一样,这有影响吗? | 没影响。任何切法的结果都相同 |
一句话:结合律给“怎么分组”自由,线段树才能在固定的树形上预先算好、又在任意查询形状上合并出同一个答案。
反例:没有结合律就失效
取“平均数”当合并运算,
两者不等。于是建树时父节点存的是“按建树切法算出的平均数”,查询时切法一变,合并出来就是另一个数, 树里存的数和查询算出的数对不上,线段树直接失效。
要在区间上求平均数,正确做法是维护“区间和 + 区间长度”,这两个量的合并满足结合律, 除法留到输出时再做。
结合律不是全部
线段树能跑还要求合并本身代价是
- 不需要交换律:线段树本来就保序,叶子顺序不换。
- 不需要幂等律:线段树的区间分解天然不重不漏,不会把同一段合并两次。
第二条值得记牢:靠“重叠两个块”来回答询问的写法(例如常见的重叠 ST 表)才需要幂等律。 带方向的合并运算在那种写法下会配出非法结果,但在线段树上完全正常。
树上区间如何划分
对节点 p 表示的区间 [l,r]:
mid = (l + r) / 2
左孩子: [l, mid]
右孩子: [mid+1, r]
如果用数组存这棵树:
1
2
left_child = p * 2
right_child = p * 2 + 1
通常开 4*n 空间。因为线段树不是完全紧凑地占用数组下标,4*n 是安全上界。
算法步骤
建树
- 当前区间是
[l,r]。 - 如果
l == r,节点值就是a[l]。 - 否则递归建立左孩子和右孩子。
- 用两个孩子的值合并出当前节点。
单点修改
- 从根节点
[1,n]出发。 - 如果目标位置
x <= mid,进入左孩子;否则进入右孩子。 - 到达叶子节点后修改值。
- 回溯时重新合并沿途所有父节点。
区间查询
- 若当前节点区间完全包含在查询区间
[L,R]中,直接返回当前节点值。 - 否则根据
[L,R]是否和左右孩子相交,递归查询相关孩子。 - 把递归结果合并。
算法证明
核心不变量:每个节点 p 始终正确维护它代表区间 [l,r] 的区间和。
建树时,叶子节点直接等于原数组值;内部节点由左右孩子求和得到,所以不变量成立。
单点修改只会影响从根到该叶子的一条路径。修改叶子后,沿路径回溯重新计算父节点,所有受影响节点被修正;其他节点对应区间不包含该位置,不需要改变。
区间查询时,被选中的节点区间两两不交,并且刚好拼成 [L,R]。每个节点的值都正确维护自己的区间和,所以合并后得到正确答案。
复杂度分析
设数组长度为
- 建树:
。 - 单点修改:
。 - 区间查询:
。 - 空间复杂度:
。
代码实现
模板输入格式:
n m
a1 a2 ... an
op ...
其中:
op = 1 x k表示a[x] += k;op = 2 l r表示查询[l,r]的区间和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 单点加 + 区间求和线段树,节点与区间均为 1 下标。
const int maxn = 100000 + 5; // 按题目规模调整,n 不能超过 maxn
ll base[maxn]; // 原始数组,建树时用 base[1..n]
ll tr[maxn << 2]; // tr[p]:节点 p 管辖区间的和
int ls(int p) { return p << 1; } // p 的左儿子 2p
int rs(int p) { return p << 1 | 1; } // p 的右儿子 2p+1
// 上推:父区间的和 = 两个儿子的和
void pushup(int p) { tr[p] = tr[ls(p)] + tr[rs(p)]; }
// 用 base[1..n] 建树
void seg_build(int p, int l, int r) {
if (l == r) {
tr[p] = base[l];
return;
}
int mid = (l + r) >> 1;
seg_build(ls(p), l, mid);
seg_build(rs(p), mid + 1, r);
pushup(p);
}
// 单点加:把位置 pos 的值加上 value,沿根到叶子的路径回溯修正
void point_add(int pos, ll value, int p, int l, int r) {
if (l == r) {
tr[p] += value;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) point_add(pos, value, ls(p), l, mid);
else point_add(pos, value, rs(p), mid + 1, r);
pushup(p);
}
// 区间和:把 [ql, qr] 拆成不交的若干节点,逐个累加
ll range_sum(int ql, int qr, int p, int l, int r) {
if (qr < l || r < ql) return 0; // 完全不相交
if (ql <= l && r <= qr) return tr[p]; // 完全被覆盖,直接取
int mid = (l + r) >> 1;
ll answer = range_sum(ql, qr, ls(p), l, mid);
answer += range_sum(ql, qr, rs(p), mid + 1, r);
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> base[i];
seg_build(1, 1, n);
while (m--) {
int op;
cin >> op;
if (op == 1) {
int x;
ll k;
cin >> x >> k;
point_add(x, k, 1, 1, n);
} else {
int l, r;
cin >> l >> r;
cout << range_sum(l, r, 1, 1, n) << '\n';
}
}
return 0;
}
Python 版与 C++ 一一对应:全局列表 base / tr 配 init(n),然后填 base[1..n]、调 seg_build(1, 1, n),再用 point_add(x, k, 1, 1, n) 与 range_sum(l, r, 1, 1, n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# 单点加 + 区间求和线段树,节点与区间均为 1 下标。
# 与 C++ 版一一对应:全局列表 base / tr,配 init(n) 与独立函数。
# 调用顺序:init(n) -> 填 base[1..n] -> seg_build(1, 1, n) -> point_add / range_sum。
# 递归深度是线段树高度 O(log n),不会触及默认递归上限。
# C++ 用 long long 存区间和防溢出;Python int 任意精度,该坑不存在。
base: list[int] = [] # 原始数组,建树时用 base[1..n]
tr: list[int] = [] # tr[p]:节点 p 管辖区间的和
n: int = 0 # 数组长度
def init(size: int) -> None:
"""重置为区间 [1, size];换一组数据前必须先调用。"""
global n, base, tr
n = size
base = [0] * (n + 1)
tr = [0] * (n * 4 + 5)
def ls(p: int) -> int:
return p << 1 # 左儿子 2p
def rs(p: int) -> int:
return p << 1 | 1 # 右儿子 2p+1
def pushup(p: int) -> None:
"""上推:父区间的和 = 两个儿子的和。"""
tr[p] = tr[ls(p)] + tr[rs(p)]
def seg_build(p: int, l: int, r: int) -> None:
"""用 base[1..n] 建树。"""
if l == r:
tr[p] = base[l]
return
mid = (l + r) >> 1
seg_build(ls(p), l, mid)
seg_build(rs(p), mid + 1, r)
pushup(p)
def point_add(pos: int, value: int, p: int, l: int, r: int) -> None:
"""单点加:把位置 pos 的值加上 value。"""
if l == r:
tr[p] += value
return
mid = (l + r) >> 1
if pos <= mid:
point_add(pos, value, ls(p), l, mid)
else:
point_add(pos, value, rs(p), mid + 1, r)
pushup(p)
def range_sum(ql: int, qr: int, p: int, l: int, r: int) -> int:
"""返回 [ql, qr] 的区间和。"""
if qr < l or r < ql:
return 0 # 完全不相交
if ql <= l and r <= qr:
return tr[p] # 完全被覆盖
mid = (l + r) >> 1
answer = range_sum(ql, qr, ls(p), l, mid)
answer += range_sum(ql, qr, rs(p), mid + 1, r)
return answer
测试用例
输入:
5 5
1 2 3 4 5
2 1 5
1 3 2
2 2 4
1 5 -1
2 4 5
输出:
15
11
8
应用分类详解
单点修改线段树的本质是维护“一个位置变化后,少数祖先区间受影响”的动态区间信息。
一、动态区间和
典型模式: 数组会单点变化,同时查询区间和。
识别信号: 出现“单点加”“区间求和”“多次操作”。
核心建模: 每个节点维护区间和,修改后向上重新合并。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 单点修改区间和 | luogu-P3374 | 线段树或树状数组均可 |
| 敌兵布阵 | HDU 1166 | 单点增减士兵数量,查询区间总数 |
二、动态区间最值
典型模式: 单点修改后,查询某段最大值或最小值。
识别信号: 出现“修改一个位置”“查询区间最大/最小”。
核心建模: 把合并操作从加法换成 max 或 min。
三、不能直接用前缀和的问题
典型模式: 数组频繁修改,静态前缀和会失效。
识别信号: 既有修改又有区间查询。
核心建模: 用树维护前缀和无法稳定处理的动态区间信息。
经典例题
1. luogu-P3374
动态区间和模板题。树状数组和线段树都可以做,适合对比两种数据结构。
2. HDU 1166 敌兵布阵
单点增减,区间求和。非常适合作为线段树入门题。
3. 区间最值模板题
把 push_up 中的加法改为 max 或 min,即可维护动态区间最值。
练习资源
- 本页保留了旧版对拍程序
check1.cpp和图示生成程序,用于手动练习线段树递归过程。