线段树:单点修改与区间查询

代码模板

线段树单点修改与区间查询的原理与实现(基础线段树)。

一句话算法

线段树把大区间不断分成左右两半,让一次修改或查询只访问和目标有关的 O(log⁡n)O(\log n) 个区间层级。

问题模型

给定长度为 nn 的数组,支持两类操作:

  1. 单点修改:a[x] += k。
  2. 区间查询:求 a[l] + ... + a[r]。

如果每次查询都扫描区间,最坏是 O(n)O(n)。线段树用一棵二叉树维护区间信息,可以把两类操作都降到 O(log⁡n)O(\log n)。

核心直觉

每个节点维护一个连续区间的答案。

例如维护区间和时:

sum([l,r]) = sum([l,mid]) + sum([mid+1,r])

这说明父节点的信息可以由两个孩子合并得到。

线段树适合维护满足“区间可合并”的信息,例如:

  • 区间和;
  • 区间最小值、最大值;
  • 区间 gcd;
  • 区间按位或、按位与。

为什么可以合并:结合律

“区间可合并”这句话的确切含义是:把两段的信息合成一段的那个运算,必须满足结合律。

设合并运算记作 ⋅\cdot,a,b,ca,b,c 是三段区间各自的信息,结合律要求

(a⋅b)⋅c=a⋅(b⋅c)(a \cdot b) \cdot c = a \cdot (b \cdot c)

意思是先合并哪一对不重要,括号加在哪里结果都一样。因此 a⋅b⋅ca \cdot b \cdot c 可以不写括号,没有歧义。

注意它和另外两条常见性质互不蕴含:

性质 式子 和结合律的关系
结合律 (a⋅b)⋅c=a⋅(b⋅c)(a \cdot b) \cdot c = a \cdot (b \cdot c) 本条
交换律 a⋅b=b⋅aa \cdot b = b \cdot a 另一件事,线段树不需要
幂等律 a⋅a=aa \cdot a = a 又一件,线段树不需要

矩阵乘法是“有结合律但没有交换律”的典型例子,可见两者完全独立。

结合律解决了什么

线段树本质上做两件事:

  1. 把 [l,r][l,r] 递归切成左右两半,直到单点;
  2. 回溯时用合并运算把两个儿子的信息合成父亲。

所以一次查询的实质是:把 [l,r][l,r] 拆成若干段,再用某种括号顺序合并起来。 结合律保证的正是“括号顺序无关”,于是下面两个问题都有了答案:

问题 结合律怎么解决
建树时父亲信息由儿子合并而来,那查询时重新合并出来的结果,会等于原始区间真实的答案吗? 会。建树和查询用的是同一批叶子、同一个顺序,只是括号不同,而结合律说明括号无关
线段树结构是固定的,但查询区间是任意的,切出来的段数和形状每次都不一样,这有影响吗? 没影响。任何切法的结果都相同

一句话:结合律给“怎么分组”自由,线段树才能在固定的树形上预先算好、又在任意查询形状上合并出同一个答案。

反例:没有结合律就失效

取“平均数”当合并运算,avg⁡(a,b)=(a+b)/2\operatorname{avg}(a,b) = (a+b)/2:

(1⋅2)⋅3=2.25,1⋅(2⋅3)=1.75(1 \cdot 2) \cdot 3 = 2.25, \qquad 1 \cdot (2 \cdot 3) = 1.75

两者不等。于是建树时父节点存的是“按建树切法算出的平均数”,查询时切法一变,合并出来就是另一个数, 树里存的数和查询算出的数对不上,线段树直接失效。

要在区间上求平均数,正确做法是维护“区间和 + 区间长度”,这两个量的合并满足结合律, 除法留到输出时再做。

结合律不是全部

线段树能跑还要求合并本身代价是 O(1)O(1)(信息量足够小),这样每层合并 O(1)O(1)、总复杂度才 O(log⁡n)O(\log n)。 另外两条性质不需要:

  • 不需要交换律:线段树本来就保序,叶子顺序不换。
  • 不需要幂等律:线段树的区间分解天然不重不漏,不会把同一段合并两次。

第二条值得记牢:靠“重叠两个块”来回答询问的写法(例如常见的重叠 ST 表)才需要幂等律。 带方向的合并运算在那种写法下会配出非法结果,但在线段树上完全正常。

树上区间如何划分

对节点 p 表示的区间 [l,r]:

mid = (l + r) / 2
左孩子: [l, mid]
右孩子: [mid+1, r]

如果用数组存这棵树:

cpp
        
1
2
left_child = p * 2 right_child = p * 2 + 1

通常开 4*n 空间。因为线段树不是完全紧凑地占用数组下标,4*n 是安全上界。

算法步骤

建树

  1. 当前区间是 [l,r]。
  2. 如果 l == r,节点值就是 a[l]。
  3. 否则递归建立左孩子和右孩子。
  4. 用两个孩子的值合并出当前节点。

单点修改

  1. 从根节点 [1,n] 出发。
  2. 如果目标位置 x <= mid,进入左孩子;否则进入右孩子。
  3. 到达叶子节点后修改值。
  4. 回溯时重新合并沿途所有父节点。

区间查询

  1. 若当前节点区间完全包含在查询区间 [L,R] 中,直接返回当前节点值。
  2. 否则根据 [L,R] 是否和左右孩子相交,递归查询相关孩子。
  3. 把递归结果合并。

算法证明

核心不变量:每个节点 p 始终正确维护它代表区间 [l,r] 的区间和。

建树时,叶子节点直接等于原数组值;内部节点由左右孩子求和得到,所以不变量成立。

单点修改只会影响从根到该叶子的一条路径。修改叶子后,沿路径回溯重新计算父节点,所有受影响节点被修正;其他节点对应区间不包含该位置,不需要改变。

区间查询时,被选中的节点区间两两不交,并且刚好拼成 [L,R]。每个节点的值都正确维护自己的区间和,所以合并后得到正确答案。

复杂度分析

设数组长度为 nn。

  • 建树:O(n)O(n)。
  • 单点修改:O(log⁡n)O(\log n)。
  • 区间查询:O(log⁡n)O(\log n)。
  • 空间复杂度:O(n)O(n)。

代码实现

模板输入格式:

n m
a1 a2 ... an
op ...

其中:

  • op = 1 x k 表示 a[x] += k;
  • op = 2 l r 表示查询 [l,r] 的区间和。
C++
cpp
        
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

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)。

python
        
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 和图示生成程序,用于手动练习线段树递归过程。