ALGORITHM NOTES阅读地图
7个主要章节
3段代码示例
12组图片与图表

先明确状态与不变量，再对照手算、证明、边界和实现。

章节速览7 节 · 展开选择

339D Xenia and Bit Operations 已经说明，线段树的核心不是“会写四倍数组”，而是找到一种能由左右孩子合并的区间摘要。本文继续用三道题检验这个观点：52C 给节点加上延迟更新，380C 的合并必须保持左右顺序，474F 则在同一节点里同时保存 GCD 与它的出现次数。

三题没有共享一份机械模板。每次都先回答三个问题：节点代表什么，两个相邻区间怎样合并，修改或查询能否只访问 O(log n) 个节点。

1. 官方信息与递进关系

以下题名、难度、标签和约束于 2026-09-14 通过 Codeforces 官方题目页核对。

题目 难度 官方标签 主要约束 本文训练点
52C · Circular RMQ 2200 data structures n,m≤2×10^5 环形区间拆分、区间加、懒标记、区间最小值
380C · Sereja and Brackets 2000 data structures、schedules length(s)≤10^6，查询数 ≤10^5 非交换合并、最大合法括号子序列
474F · Ant colony 2100 data structures、math、number theory n,t≤10^5，s[i]≤10^9 GCD 性质、复合摘要、频次统计

三题分别改变线段树的一个维度：52C 改变更新方式，380C 改变节点含义，474F 改变从题意到摘要的推导。

2. 第一题：52C Circular RMQ

八个叶子的线段树中，查询闭区间2到5由两个高亮节点2到3和4到5覆盖。
图解 · 区间查询选中的是一组完整节点

用 8 个叶子的普通线段树示意闭区间 [2,5]：它分解成 [2,3] 与 [4,5]，不必逐个扫描叶子。先把环形查询拆成普通区间，再按正文的摘要规则合并；这张图不表示所有查询都只需两个节点。

查看完整图示

2.1 题目与朴素方法

长度为 n 的环形数组支持两种操作：给环形区间 [l,r] 的每个元素加 v，或查询该区间最小值。下标从 0 开始；当 l>r 时，区间经过数组末尾再绕回开头，例如 n=5 时 [3,1] 表示下标 3,4,0,1。

逐元素修改或扫描一次需要 O(n)，最多二十万次操作会退化到 O(nm)。普通前缀最小值也不适用，因为数组会反复修改，而且“最小值”不能像区间和那样通过两个前缀相减得到。

环形本身不需要新数据结构。先把它拆成普通区间：

条件 环形区间对应的普通区间
l≤r 一个区间 [l,r]
l>r 两个区间 [l,n-1] 与 [0,r]

更新分别执行两次；查询取两段最小值的较小者。真正困难的部分变成普通数组上的“区间加 + 区间最小值”。

2.2 节点摘要与懒标记

对每个节点保存：

  • tree[node]：这个节点区间当前的最小值，已经包含作用在它上面的全部更新；
  • lazy[node]：整段都应增加、但还没有下传给孩子的增量。

若一次更新完整覆盖节点区间，区间中所有数同时加 v，最小值也恰好加 v。因此只需执行：

1
2
tree[node] += v
lazy[node] += v

暂时不访问孩子。只有后续操作需要进入孩子时，才把 lazy[node] 同时加给左右孩子并清零，这就是延迟传播。

2.3 为什么不能只改 tree

假设节点 [0,3] 整段加 5。如果只令根的最小值加 5，却不记录 lazy，随后查询 [0,1] 时会进入左孩子；左孩子仍保存旧值，更新就像从未发生过。

反过来，只记录 lazy 而不更新 tree 也不行：若后续查询恰好完整覆盖 [0,3]，算法会直接返回根摘要，却得到加法前的最小值。tree 保证当前节点可直接回答，lazy 保证需要下钻时孩子能够补上历史。

2.4 官方样例手算

初始数组为 [1,2,3,4]：

操作 拆分 操作后的数组或答案
查询 [3,0] [3,3] 与 [0,0] min(4,1)=1
[3,0] 加 -1 两个单点区间 [0,2,3,3]
查询 [0,1] 不跨界 min(0,2)=0
查询 [2,1] [2,3] 与 [0,1] 全数组最小值为 0

2.5 正确性证明

节点不变量： tree[node] 始终等于该节点区间应用全部已发生更新后的最小值，lazy[node] 等于尚未写入孩子摘要的整段增量。

建树时叶子等于原数组，内部节点取孩子最小值，不变量成立。完整覆盖更新时，区间所有元素同加 v，其最小值也同加 v；把 v 累加进懒标记，准确记录尚未下传的影响。部分覆盖前先下传，再更新相交孩子并重新取最小值，因此不变量继续成立。

查询完整覆盖时由不变量可直接返回。部分覆盖前下传，递归结果分别是相交子区间的最小值，取两者较小值即为目标区间最小值。环形区间拆分包含且只包含原操作下标，所以一次或两次普通查询都正确。

2.6 完整 C++17 实现

更新值累积后可能达到约 2×10^11，数组、树和懒标记都使用 long long。操作行有两个或三个整数，因此用 getline 与 stringstream 判断类型。

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <algorithm>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

class SegmentTree {
public:
    explicit SegmentTree(const vector<long long>& values)
        : size(static_cast<int>(values.size())), tree(4 * size), lazy(4 * size, 0) {
        build(1, 0, size - 1, values);
    }

    void add(int left, int right, long long value) {
        add(1, 0, size - 1, left, right, value);
    }

    long long minimum(int left, int right) {
        return minimum(1, 0, size - 1, left, right);
    }

private:
    int size;
    vector<long long> tree;
    vector<long long> lazy;

    void build(int node, int begin, int end, const vector<long long>& values) {
        if (begin == end) {
            tree[node] = values[begin];
            return;
        }
        int middle = (begin + end) / 2;
        build(node * 2, begin, middle, values);
        build(node * 2 + 1, middle + 1, end, values);
        tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    }

    void apply(int node, long long value) {
        tree[node] += value;
        lazy[node] += value;
    }

    void push(int node) {
        if (lazy[node] == 0) return;
        apply(node * 2, lazy[node]);
        apply(node * 2 + 1, lazy[node]);
        lazy[node] = 0;
    }

    void add(int node, int begin, int end, int left, int right, long long value) {
        if (left <= begin && end <= right) {
            apply(node, value);
            return;
        }
        push(node);
        int middle = (begin + end) / 2;
        if (left <= middle) add(node * 2, begin, middle, left, right, value);
        if (right > middle) add(node * 2 + 1, middle + 1, end, left, right, value);
        tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    }

    long long minimum(int node, int begin, int end, int left, int right) {
        if (left <= begin && end <= right) return tree[node];
        push(node);
        int middle = (begin + end) / 2;
        long long answer = numeric_limits<long long>::max();
        if (left <= middle) answer = min(answer, minimum(node * 2, begin, middle, left, right));
        if (right > middle) answer = min(answer, minimum(node * 2 + 1, middle + 1, end, left, right));
        return answer;
    }
};

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

    int n;
    cin >> n;
    vector<long long> values(n);
    for (long long& value : values) cin >> value;

    SegmentTree tree(values);
    int operations;
    cin >> operations;
    string line;
    getline(cin, line);

    while (operations--) {
        getline(cin, line);
        stringstream input(line);
        vector<long long> parts;
        long long value;
        while (input >> value) parts.push_back(value);

        int left = static_cast<int>(parts[0]);
        int right = static_cast<int>(parts[1]);
        if (parts.size() == 3) {
            long long increment = parts[2];
            if (left <= right) {
                tree.add(left, right, increment);
            } else {
                tree.add(left, n - 1, increment);
                tree.add(0, right, increment);
            }
        } else {
            long long answer;
            if (left <= right) {
                answer = tree.minimum(left, right);
            } else {
                answer = min(tree.minimum(left, n - 1), tree.minimum(0, right));
            }
            cout << answer << '\n';
        }
    }
}

每个普通区间操作为 O(log n)；环形操作最多拆成两段，数量级不变。建树 O(n)，总时间 O(n+m log n)，空间 O(n)。

3. 第二题：380C Sereja and Brackets

3.1 为什么区间和不够

给定只含左右括号的字符串，每次查询子串 [l,r] 中最长合法括号子序列的长度。子序列可以删除字符，但不能改变剩余字符的相对顺序。

把左括号记为 +1、右括号记为 -1，区间和只能告诉我们数量差，不能告诉顺序。) ( 与 ( ) 的和都为 0，前者无法组成合法括号，后者答案为 2。

一个区间处理完内部能匹配的括号后，只需保留三项：

  • matched：已经匹配的括号对数；
  • open：仍未匹配的左括号数；
  • close：仍未匹配的右括号数。

3.2 左右孩子怎样合并

设左孩子为 L，右孩子为 R。新的跨边界匹配只能使用左侧未匹配左括号与右侧未匹配右括号：

1
2
3
4
cross = min(L.open, R.close)
matched = L.matched + R.matched + cross
open = L.open + R.open - cross
close = L.close + R.close - cross

不能反过来用 R.open 匹配 L.close，因为那会让右括号出现在左括号之前。这个合并满足结合律，却不满足交换律；查询时必须保持区间从左到右的顺序。

3.3 合并为何得到最大值

左右区间内部的最优匹配可以先独立保留。跨边界时，左段未匹配的左括号都早于右段未匹配的右括号，所以任取一对都满足顺序；最多能新增两者数量的较小值 cross。

任何跨边界合法括号对也只能来自这两个集合，因此不可能超过 cross。内部最优值与最大跨边界值相加，正是合并区间的最优匹配对数。

3.4 手工合并

字符串片段 (() 与 ))( 分别摘要为：

区间 已匹配对 未匹配左括号 未匹配右括号
(() 1 1 0
))( 0 1 2

跨边界可以再匹配 min(1,2)=1 对，合并结果为 matched=2, open=1, close=1，最长合法括号子序列长度是 2×matched=4。

3.5 正确性证明

叶子 ( 的摘要为 (0,1,0)，叶子 ) 为 (0,0,1)，显然正确。假设左右孩子摘要都准确记录各自最大内部匹配及剩余括号，根据上一节的上界与构造，合并新增的最大匹配数恰为 min(L.open,R.close)，扣除这些括号后剩余计数也准确。因此归纳可知所有节点摘要正确。

查询把目标区间拆成按原顺序排列的若干节点，再依次使用同一合并。结合律保证不同树形分组不改变结果，保持左右顺序则保证括号先后关系不被破坏，最终 2×matched 就是最长合法括号子序列长度。

3.6 完整 C++17 实现

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 <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Node {
    int matched = 0;
    int open = 0;
    int close = 0;
};

Node mergeNodes(const Node& left, const Node& right) {
    int cross = min(left.open, right.close);
    return {
        left.matched + right.matched + cross,
        left.open + right.open - cross,
        left.close + right.close - cross,
    };
}

class SegmentTree {
public:
    explicit SegmentTree(const string& brackets)
        : size(static_cast<int>(brackets.size())), tree(4 * size) {
        build(1, 0, size - 1, brackets);
    }

    Node query(int left, int right) const {
        return query(1, 0, size - 1, left, right);
    }

private:
    int size;
    vector<Node> tree;

    void build(int node, int begin, int end, const string& brackets) {
        if (begin == end) {
            tree[node] = brackets[begin] == '(' ? Node{0, 1, 0} : Node{0, 0, 1};
            return;
        }
        int middle = (begin + end) / 2;
        build(node * 2, begin, middle, brackets);
        build(node * 2 + 1, middle + 1, end, brackets);
        tree[node] = mergeNodes(tree[node * 2], tree[node * 2 + 1]);
    }

    Node query(int node, int begin, int end, int left, int right) const {
        if (left <= begin && end <= right) return tree[node];
        int middle = (begin + end) / 2;
        if (right <= middle) return query(node * 2, begin, middle, left, right);
        if (left > middle) return query(node * 2 + 1, middle + 1, end, left, right);
        Node leftResult = query(node * 2, begin, middle, left, right);
        Node rightResult = query(node * 2 + 1, middle + 1, end, left, right);
        return mergeNodes(leftResult, rightResult);
    }
};

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

    string brackets;
    cin >> brackets;
    SegmentTree tree(brackets);

    int queries;
    cin >> queries;
    while (queries--) {
        int left, right;
        cin >> left >> right;
        Node answer = tree.query(left - 1, right - 1);
        cout << 2 * answer.matched << '\n';
    }
}

建树 O(n)，每次查询 O(log n)，总时间 O(n+m log n)。三个 int 数组随树节点一起占 O(n) 空间，在 n=10^6 时仍低于 256 MB 限制。

4. 第三题：474F Ant colony

4.1 从战斗规则提取数论条件

一次查询选择 [l,r]。区间内每对蚂蚁都战斗；若蚂蚁 i 的力量 s[i] 能整除对手力量，它就在这场战斗得分。只有对区间内其他每只蚂蚁都能得分的个体会被放走，求被吃掉的数量。

直接为每只蚂蚁检查所有对手，一次查询最坏为区间长度平方。关键是把“整除所有数”与区间 GCD 联系起来。

设区间最大公约数为 g。一只力量为 x 的蚂蚁能够整除区间所有力量，当且仅当 x=g：

  • 若 x 整除所有数，x 是公共因数，所以 x 整除 g；
  • g 又整除区间每个数，当然也整除 x；
  • 两个正整数互相整除，只能相等；
  • 反过来，力量恰为 g 时，按 GCD 定义它一定整除所有数。

所以幸存数就是区间内等于 GCD 的元素个数，答案为：

1
区间长度 - GCD 在区间中的出现次数

4.2 节点为什么要保存两个量

节点摘要为 (gcdValue,count)：gcdValue 是整段 GCD，count 是段内恰好等于该 GCD 的元素数。

合并左右孩子时，先求：

1
g = gcd(left.gcdValue, right.gcdValue)

若某个孩子的 GCD 等于 g，它内部等于自身 GCD 的那些位置也等于合并后的 g，应把计数加入。若孩子 GCD 大于 g，孩子中不可能存在值恰为 g：孩子的每个元素都是其 GCD 的正倍数。

1
2
count = (left.gcdValue == g ? left.count : 0)
      + (right.gcdValue == g ? right.count : 0)

4.3 官方样例手算

力量为 [1,3,2,4,2]：

查询 区间 GCD 等于 GCD 的个数 被吃数量
[1,5] 1 1 5-1=4
[2,5] 1 0 4-0=4
[3,5] 2 2 3-2=1
[4,5] 2 1 2-1=1

第二行说明“区间 GCD 是 1”不代表一定有力量为 1 的蚂蚁；因此节点不能只保存 GCD，还要同时保存其真实出现次数。

4.4 正确性证明

叶子力量为 x，摘要 (x,1) 显然正确。假设左右孩子摘要正确，合并后的 GCD 由最大公约数结合律得到。一个元素等于合并 GCD，只可能来自 GCD 同样等于该值的孩子；相应孩子的 count 已准确统计这些元素，条件相加便得到完整频次。因此所有节点摘要归纳成立。

查询按区间顺序合并覆盖节点，GCD 的结合律以及上述计数规则保证得到目标区间的 GCD 和出现次数。根据“能整除全部力量当且仅当自身等于区间 GCD”的等价关系，用区间长度减去该频次，正是被吃掉的蚂蚁数。

4.5 完整 C++17 实现

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
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

struct Node {
    int gcdValue = 0;
    int count = 0;
};

Node mergeNodes(const Node& left, const Node& right) {
    int value = gcd(left.gcdValue, right.gcdValue);
    int count = 0;
    if (left.gcdValue == value) count += left.count;
    if (right.gcdValue == value) count += right.count;
    return {value, count};
}

class SegmentTree {
public:
    explicit SegmentTree(const vector<int>& values)
        : size(static_cast<int>(values.size())), tree(4 * size) {
        build(1, 0, size - 1, values);
    }

    Node query(int left, int right) const {
        return query(1, 0, size - 1, left, right);
    }

private:
    int size;
    vector<Node> tree;

    void build(int node, int begin, int end, const vector<int>& values) {
        if (begin == end) {
            tree[node] = {values[begin], 1};
            return;
        }
        int middle = (begin + end) / 2;
        build(node * 2, begin, middle, values);
        build(node * 2 + 1, middle + 1, end, values);
        tree[node] = mergeNodes(tree[node * 2], tree[node * 2 + 1]);
    }

    Node query(int node, int begin, int end, int left, int right) const {
        if (left <= begin && end <= right) return tree[node];
        int middle = (begin + end) / 2;
        if (right <= middle) return query(node * 2, begin, middle, left, right);
        if (left > middle) return query(node * 2 + 1, middle + 1, end, left, right);
        Node leftResult = query(node * 2, begin, middle, left, right);
        Node rightResult = query(node * 2 + 1, middle + 1, end, left, right);
        return mergeNodes(leftResult, rightResult);
    }
};

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

    int n;
    cin >> n;
    vector<int> strength(n);
    for (int& value : strength) cin >> value;

    SegmentTree tree(strength);
    int queries;
    cin >> queries;
    while (queries--) {
        int left, right;
        cin >> left >> right;
        Node result = tree.query(left - 1, right - 1);
        cout << right - left + 1 - result.count << '\n';
    }
}

建树 O(n)，每次查询访问 O(log n) 个节点；每次合并做常数次 GCD 与比较，总时间 O(n+t log n)，空间 O(n)。

5. 三题放在一起比较

题目 节点摘要 合并是否交换 是否修改 最容易漏掉的条件
52C 区间最小值、待下传增量 min 可交换 区间加 环形区间要拆分，增量需用 long long
380C 已匹配对、剩余左括号、剩余右括号 不可交换 无 左段右括号不能与右段左括号倒序配对
474F 区间 GCD、等于 GCD 的频次 可交换 无 GCD 可能没有在区间中出现

统一的设计步骤

  1. 先写出查询真正需要的答案，判断单个标量是否足够；
  2. 假设左右孩子摘要已经正确，手工推导合并式；
  3. 检查合并是否满足结合律，以及左右次序能否交换；
  4. 若有区间修改，推导它怎样直接作用于节点摘要；
  5. 用单点、整段、跨中点、重复值与数值上限验证边界。

6. 错误清单

场景 常见错误 后果
52C l>r 当成空区间或交换端点 修改、查询了错误的下标集合
52C 完整覆盖 只改 tree，不累计 lazy 后续子区间查询丢失更新
52C 多次大增量 使用 int 累积结果溢出
380C 合并 使用 min(left.close,right.open) 把顺序相反的括号错误配对
380C 输出 输出匹配对数 题目要字符长度，应乘 2
380C 查询 交换左右部分的合并顺序 非交换摘要被破坏
474F 判断幸存 只判断区间最小值 最小值未必整除所有元素
474F 只存 GCD 默认 GCD 一定出现 如 [6,10] 的 GCD 2 不在区间中
474F 单点查询 输出 1 唯一蚂蚁无需被吃，答案为 0

7. 独立验证

tests/verify-segment-tree-three-article.cjs 会提取本文三段 C++17，以 -Wall -Wextra -pedantic 编译并要求零警告。三套参考方法刻意不复用正文线段树：

  • 52C 在小数组上逐元素执行环形修改并直接扫描最小值；
  • 380C 对查询子串从左到右贪心配对括号；
  • 474F 为区间内每只蚂蚁逐一检查它是否整除所有其他力量。

验证覆盖官方样例、随机操作、跨数组末尾的区间、负增量、全左或全右括号、GCD 不在区间中、重复力量与单点查询。大数据还覆盖 n=2×10^5 的十万次区间操作、长度一百万的括号串，以及十万次蚂蚁查询。

线段树真正可迁移的能力，是把题意压缩成“足以合并的最小信息”。下一次遇到区间题时，先尝试在纸上合并两个相邻小区间；如果必须回看所有原始元素，说明摘要还不够，或这道题需要另一种结构。