我的算法书 - 线段树：单点修改与区间查询

一句话算法

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

问题模型

给定长度为 $n$ 的数组，支持两类操作：

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

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

核心直觉

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

例如维护区间和时：

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

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

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

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

树上区间如何划分

对节点 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 是安全上界。

算法步骤

建树

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

单点修改

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

区间查询

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

算法证明

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

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

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

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

复杂度分析

设数组长度为 $n$ 。

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

代码实现

模板输入格式：

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

其中：

op = 1 x k 表示 a[x] += k；
op = 2 l r 表示查询 [l,r] 的区间和。

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
77
78
79
80
81
82
83
84
85
86

        #include <bits/stdc++.h>
using namespace std;

template <typename T>
struct SegmentTreePointAdd {
    int n = 0;
    vector<T> tree;

    SegmentTreePointAdd(int n = 0) {
        init(n);
    }

    void init(int size) {
        n = size;
        tree.assign(n * 4 + 5, 0);
    }

    void pull(int p) {
        tree[p] = tree[p << 1] + tree[p << 1 | 1];
    }

    void build(const vector<T> &a, int l, int r, int p = 1) {
        if (l == r) {
            tree[p] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(a, l, mid, p << 1);
        build(a, mid + 1, r, p << 1 | 1);
        pull(p);
    }

    void add(int pos, T value, int l, int r, int p = 1) {
        if (l == r) {
            tree[p] += value;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) add(pos, value, l, mid, p << 1);
        else add(pos, value, mid + 1, r, p << 1 | 1);
        pull(p);
    }

    T query(int ql, int qr, int l, int r, int p = 1) const {
        if (ql <= l && r <= qr) return tree[p];

        int mid = (l + r) >> 1;
        T answer = 0;
        if (ql <= mid) answer += query(ql, qr, l, mid, p << 1);
        if (qr > mid) answer += query(ql, qr, mid + 1, r, p << 1 | 1);
        return answer;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    SegmentTreePointAdd<long long> seg(n);
    seg.build(a, 1, n);

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            long long k;
            cin >> x >> k;
            seg.add(x, k, 1, n);
        } else {
            int l, r;
            cin >> l >> r;
            cout << seg.query(l, r, 1, n) << '\n';
        }
    }

    return 0;
}

测试用例

输入：

输出：

15
11
8

应用分类详解

单点修改线段树的本质是维护“一个位置变化后，少数祖先区间受影响”的动态区间信息。

一、动态区间和

典型模式： 数组会单点变化，同时查询区间和。

识别信号： 出现“单点加”“区间求和”“多次操作”。

核心建模： 每个节点维护区间和，修改后向上重新合并。

应用场景	经典题目	核心思路
单点修改区间和	luogu-P3374	线段树或树状数组均可
敌兵布阵	HDU 1166	单点增减士兵数量，查询区间总数

二、动态区间最值

典型模式： 单点修改后，查询某段最大值或最小值。

识别信号： 出现“修改一个位置”“查询区间最大/最小”。

核心建模： 把合并操作从加法换成 max 或 min。

三、不能直接用前缀和的问题

典型模式： 数组频繁修改，静态前缀和会失效。

识别信号： 既有修改又有区间查询。

核心建模： 用树维护前缀和无法稳定处理的动态区间信息。

经典例题

1. luogu-P3374

动态区间和模板题。树状数组和线段树都可以做，适合对比两种数据结构。

2. HDU 1166 敌兵布阵

单点增减，区间求和。非常适合作为线段树入门题。

3. 区间最值模板题

把 pull 中的加法改为 max 或 min，即可维护动态区间最值。

练习资源

本页保留了旧版对拍程序 check1.cpp 和图示生成程序，用于手动练习线段树递归过程。