并查集#

算法基础课的内容：并查集可以在 $O(\log n)$ 的时间复杂度下进行合并两个集合、查询某个元素的祖宗节点的操作。并查集有两个扩展功能：

记录每个集合的大小（绑定到根节点）

记录每个点到根节点的距离（绑定到每个元素上）

格子游戏（裸并查集）#

转换为图论问题，采用并查集处理连通性问题。

需要将二维坐标转化为一维，存在以下公式： $g[i][j]=l[n*i+j]$ ， $i, j$ 从零开始。

Code#

1
// Problem: 格子游戏
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1252/
4
// Time: 2026-04-19 17:25:55
5
#include <iostream>
6
using namespace std;
7
const int N = 40010;
8

9
int n, m, p[N];
10

11
int find(int x)
12
{
13
    if (p[x] != x)
14
        p[x] = find(p[x]);
15
    return p[x];
16
}
17

18
int main()
19
{
20
    cin >> n >> m;
21
    for (int i = 1; i <= n * n; i++)
22
        p[i] = i;
23

24
    int res = 0;
25
    for (int i = 1; i <= m; i++)
26
    {
27
        int x, y;
28
        char c;
29
        cin >> x >> y >> c;
30

31
        x--, y--;
32

33
        auto get = [&](int x, int y) -> int { return x * n + y; }; // 一维坐标
34

35
        int a = get(x, y);
36
        int b;
37

38
        if (c == 'D')
39
            b = get(x + 1, y);
40
        else
41
            b = get(x, y + 1);
42

43
        int pa = find(a), pb = find(b);
44
        if (pa == pb)
45
        {
46
            res = i;
47
            break;
48
        }
49
        p[pa] = pb;
50
    }
51

52
    if (!res)
53
        puts("draw");
54
    else
55
        cout << res << endl;
56

57
    return 0;
58
}

搭配购买（并查集 +01 背包）#

解题思路：

使用并查集，维护搭配的物品组，并在根节点上维护每堆云的总体积、总价值
遍历所有 p[x] = x 的根节点，用 01 背包板子即可

Code#

1
// Problem: 搭配购买
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/1254/
4
// Time: 2026-04-19 17:40:22
5
#include <bits/stdc++.h>
6
using namespace std;
7
const int N = 10010;
8

9
int n, m, val;
10
int v[N], w[N], p[N], f[N];
11

12
int find(int x)
13
{
14
    if (p[x] != x)
15
        p[x] = find(p[x]);
16
    return p[x];
17
}
18

19
int main()
20
{
21
    cin >> n >> m >> val;
22

23
    for (int i = 1; i <= n; i++)
24
        p[i] = i;
25

26
    for (int i = 1; i <= n; i++)
27
        cin >> v[i] >> w[i];
28

29
    while (m--)
30
    {
31
        int a, b;
32
        cin >> a >> b;
33
        int pa = find(a), pb = find(b);
34

35
        if (pa != pb)
36
        {
37
            v[pb] += v[pa];
38
            w[pb] += w[pa];
39
            p[pa] = pb;
40
        }
41
    }
42

43
    for (int i = 1; i <= n; i++)
44
        if (p[i] == i)
45
            for (int j = val; j >= v[i]; j--)
46
                f[j] = max(f[j], f[j - v[i]] + w[i]);
47

48
    cout << f[val] << endl;
49
    return 0;
50
}

程序自动分析（并查集 + 离散化）#

要合并的数非常大，但只用到 $2*10^5$ 个，因此考虑离散化。

对于给定的所有约束条件，我们作以下的讨论：

对于相等的约束，我们合并到几个集合里，在这个过程中一定不会出现矛盾
对于不等的约束，如果他们已经在一个集合里，就出现矛盾了

注意不能边读边做，应该先处理相等约束，再判断不等约束的矛盾性

Code#

1
// Problem: 程序自动分析
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/239/
4
// Time: 2026-04-20 22:56:28
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14

15
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
16
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
17
const int inf = 0x3f3f3f3f;
18
const int N = 2e5 + 10;
19

20
int p[N];
21
int n, m;
22
unordered_map<int, int> mp;
23

24
struct Query
25
{
26
    int x, y, e;
27
} query[N];
28

29
int get(int x) // 如果x之前没有出现过，就分配一个唯一的值
30
{
31
    if (mp.count(x) == 0)
32
        mp[x] = ++n;
33
    return mp[x];
34
}
35

36
int find(int x)
37
{
38
    if (p[x] != x)
39
        p[x] = find(p[x]);
40
    return p[x];
41
}
42

43
void solve()
44
{
45
    n = 0;
46
    mp.clear();
47
    cin >> m;
48

49
    for (int i = 0; i < m; i++) // 读入所有约束条件
50
    {
51
        int x, y, e;
52
        cin >> x >> y >> e;
53
        query[i] = {get(x), get(y), e};
54
    }
55

56
    for (int i = 1; i <= n; i++)
57
        p[i] = i;
58

59
    for (int i = 0; i < m; i++) // 合并相等约束条件
60
        if (query[i].e == 1)
61
        {
62
            int pa = find(query[i].x), pb = find(query[i].y);
63
            p[pa] = pb;
64
        }
65

66
    bool flag = false;
67
    for (int i = 0; i < m; i++)
68
        if (query[i].e == 0)
69
        {
70
            int pa = find(query[i].x), pb = find(query[i].y);
71
            if (pa == pb)
72
            {
73
                flag = true;
74
                break;
75
            }
76
        }
77
    if (flag)
78
        cout << "NO" << endl;
79
    else
80
        cout << "YES" << endl;
81
}
82

83
int main()
84
{
85
    int T;
86
    cin >> T;
87
    while (T--)
88
        solve();
89
    return 0;
90
}

银河英雄传说（带权并查集）#

由于题目询问间隔多少战舰，我们需要在表示集合关系的并查集的基础上引入“权值”

我们考虑记录每一个点到根节点的距离，使用前缀和来维护

根据询问“间隔多少战舰”，我们需要把距离的绝对值减去 1，当 x == y 时，特判返回 -1

维护思路#

将每个集合的大小绑定在根节点上，每个点到根节点的距离绑定到每个元素上 size[x] 表示集合的大小，d[x] 表示 x 到 p[x] 的距离
将第 a 列的船接在第 b 列的末尾，相当于让每个点到 pb 的距离都加上 size[pb]，由于路径压缩，只需要将 pa 到 pb 的距离更新成 size[pb] 即可，即 d[pa] = size[pb]

路径压缩思路#

首先找到根节点 root
计算父节点到上一个父节点的距离 d[p[x]]，并进行路径压缩，压缩后，上一个父节点即为 root
d[x] 的初始值是 x 到 p[x] 的距离，更新 d[x]，即 d[x] = d[x] + d[p[x]]

Code#

1
// Problem: 银河英雄传说
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/240/
4
// Time: 2026-04-21 13:18:46
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14

15
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
16
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
17
const int inf = 0x3f3f3f3f;
18
const int N = 30010;
19

20
int m;
21
int p[N], sz[N], d[N];
22

23
int find(int x)
24
{
25
    if (p[x] != x)
26
    {
27
        int root = find(p[x]);
28
        d[x] += d[p[x]];
29
        p[x] = root;
30
    }
31
    return p[x];
32
}
33

34
int main()
35
{
36
    cin >> m;
37

38
    for (int i = 1; i < N; i++)
39
    {
40
        p[i] = i;
41
        sz[i] = 1;
42
    }
43

44
    while (m--)
45
    {
46
        char op;
47
        int a, b;
48
        cin >> op >> a >> b;
49

50
        if (op == 'M')
51
        {
52
            int pa = find(a), pb = find(b);
53
            if (pa != pb)
54
            {
55
                d[pa] = sz[pb];
56
                sz[pb] += sz[pa];
57
                p[pa] = pb;
58
            }
59
        }
60
        if (op == 'C')
61
        {
62
            int pa = find(a), pb = find(b);
63
            if (pa != pb)
64
                cout << "-1" << endl;
65
            else
66
                cout << max(0, abs(d[a] - d[b]) - 1) << endl;
67
        }
68
    }
69
    return 0;
70
}

树状数组#

树状数组是一种支持单点修改和区间查询的，短小精悍的数据结构。可以在 $O(logn)$ 的时间复杂度下同时实现：快速求前缀和、修改某一个数。 有时，在差分数组和辅助数组的帮助下，树状数组还可解决更强的区间加单点值和区间加区间和问题，但树状数组只能解决区间和相关问题。

当题目有以下特征时，可以使用树状数组维护信息：

树状数组天然适合维护具有可逆性（存在逆元）且满足结合律的信息。例如区间和或区间异或和。

树状数组本质上维护的是前缀信息。当你需要查询区间 $[L, R]$ 的信息时，它实际上是通过 $Query(R) - Query(L-1)$ 来计算的。这就要求信息能够“相减”。

基本思想#

用二进制拆分区间#

对于长度为 $x$ 的数组，它可以用二进制来拆分：

$x = 2^{i_k} + 2^{i_{k-1}} + \dots + 2^{i_1}$ ，其中 $i_k$ 也表示长度

$i_k \geq i_{k-1} \geq i_{k-2} \geq \dots \geq i_1$ ，可知即使最坏情况下， $k \leqslant logx$

那么原来长度为 $x$ 的数组可以被划分多个区间：

$(x - 2^{i_1}, x]$ ，其中包含 $2^{i_1}$ 个数

$(x - 2^{i_1} - 2^{i_{2}}, x - 2^{i_1}]$ ，其中包含 $2^{i_2}$ 个数

$(0, x - 2^{i_1} - 2^{i_{2}} - 2^{i_{k-1}}]$ ，其中包含 $2^{i_k}$ 个数

则有如下规律：对于任意区间 (L,R]，它的长度一定是 R 的二进制表示的最后一位 1 所对应的次幂，即 $(R-lowbit(R)+1,R]$

用数组表示区间#

定义数组 c[x] = a[x - lowbit(x) + 1, x] 表示原数组 a[] 中以 x 为右端点，长度是 lowbit(x) 的区间的所有数的和。

不难发现，对于每一个数 x，1~x 所有数的和在数组 c[] 中可以拆成 logx 个数的和

不同的 c[x] 之间的关系如下图所示

抽象出树结构#

解释：

每个结点 c[x] 保存以 x 为根的子树中叶结点值的和
每个结点覆盖的长度为 lowbit(x)
c[x] 结点的父结点为 c[x + lowbit(x)]
树的深度为 log2n+1

基本功能：单点修改、区间查询

使用差分树状数组可以实现：区间修改、单点查询

初始化#

基于下文单点修改的初始化方案，时间复杂度 $O(nlogn)$ ，最常用

1
for (int i = 1; i <= n; i++)
2
    add(i, a[i]);

对于每一个节点 x，寻找它的所有子节点，不断添加树边

1
for (int i = x - 1; i; i -= lowbit(i))
2
{
3
    tr[i] += a[i];
4
    tr[x] += tr[i];
5
}

预处理出前缀和数组

由于 tr[i] 表示的区间为 $[i-lowbit(i)+1,i]$

那么可以预处理出前缀和数组再计算 tr 数组

1
for (int i = 1; i <= n; i++)
2
    tr[i] = sum[i] - sum[i - lowbit(i)];

单点修改（自下而上）#

单点修改操作，对应从子节点找到父节点，即找到包含点 x 的所有区间，并修改

根据树状数组的性质，每一个点修改后，所直接影响的节点是唯一的

设节点 x 的父节点为 p，则 p = x + lowbit(x)，修改时从下往上迭代，最多影响 log2x 个节点

1
void add(int x, int k)
2
{
3
    for(int i = x; i <= n; i += lowbit(i))
4
        t[i] += k;
5
}

区间查询（从上到下）#

区间查询操作，对应从父节点找到子节点，即查询原数组中 a[1]~a[x] 的和

1
int sum(int x)
2
{
3
    int res = 0;
4
    for(int i = x; i; i -= lowbit(i))
5
        res += t[i];
6
    return res;
7
}

可以使用前缀和思想求出任意区间 a[l] ~ a[r] 的和：sum[r] - sum[l + 1]

题目#

单点修改、区间查询#

本题要求进行两种操作：将某一个数加上 x，求某区间的区间和

裸树状数组即可实现

1
// Problem: Luogu P3374
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P3374
4
// Time: 2026-02-26 19:31:02
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8
const int N = 500010;
9

10
int a[N], tr[N];
11
int n, m;
12

13
int lowbit(int x)
14
{
15
    return x & (-x);
16
}
17

18
void add(int x, int k)
19
{
20
    for (int i = x; i <= n; i += lowbit(i))
21
        tr[i] += k;
22
}
23

24
long long query(int x)
25
{
26
    long long sum = 0;
27

28
    for (int i = x; i; i -= lowbit(i))
29
        sum += tr[i];
30

31
    return sum;
32
}
33

34
int main()
35
{
36
    cin >> n >> m;
37

38
    for (int i = 1; i <= n; i++)
39
    {
40
        cin >> a[i];
41
        add(i, a[i]);
42
    }
43

44
    while (m--)
45
    {
46
        int op;
47
        cin >> op;
48

49
        if (op == 1)
50
        {
51
            int x, k;
52
            cin >> x >> k;
53
            add(x, k);
54
        }
55

56
        if (op == 2)
57
        {
58
            int x, y;
59
            cin >> x >> y;
60
            cout << query(y) - query(x - 1) << endl;
61
        }
62
    }
63
    return 0;
64
}

区间修改、单点查询#

前置知识：

本题需要进行两种操作：将某区间每一个数加上 x，求出某一个数的值

即：区间加单点值问题

根据差分的思想，建立并维护一个存储差分信息的树状数组即可

1
// Problem: Luogu P3368
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P3368
4
// Time: 2026-02-26 22:05:33
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8
const int N = 500010;
9

10
int n, m;
11
int a[N], tr[N];
12

13
int lowbit(int x)
14
{
15
    return x & -x;
16
}
17

18
void add(int x, int c)
19
{
20
    for (int i = x; i <= n; i += lowbit(i))
21
        tr[i] += c;
22
}
23

24
long long query(int x)
25
{
26
    long long res = 0;
27
    for (int i = x; i; i -= lowbit(i))
28
        res += tr[i];
29

30
    return res;
31
}
32

33
int main()
34
{
35
    cin >> n >> m;
36
    for (int i = 1; i <= n; i++)
37
    {
38
        cin >> a[i];
39
        add(i, a[i] - a[i - 1]);
40
    }
41

42
    while (m--)
43
    {
44
        int op;
45
        cin >> op;
46

47
        if (op == 1)
48
        {
49
            int l, r, k;
50
            cin >> l >> r >> k;
51

52
            add(l, k);
53
            add(r + 1, -k);
54
        }
55

56
        if (op == 2)
57
        {
58
            int x;
59
            cin >> x;
60
            cout << query(x) << endl;
61
        }
62
    }
63
    return 0;
64
}

区间修改、区间查询#

区间修改问题依然使用差分的思想做：

a[l ~ r] += c 等价于 b[l] += c && b[r + 1] -= c

对于区间求和问题，需要使用树状数组维护两个前缀和数组：b[i] 和 i * b[i]

推导如下：

1
// Problem: 一个简单的整数问题2
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/description/244/
4
// Time: 2026-02-27 06:11:08
5
#include <bits/stdc++.h>
6
using namespace std;
7
typedef long long LL;
8
const int N = 100010;
9

10
int n, m;
11
int a[N];
12
LL tr1[N]; // 差分数组b[i]的前缀和
13
LL tr2[N]; // 差分数组b[i] * i的前缀和
14

15
int lowbit(int x)
16
{
17
    return x & -x;
18
}
19

20
void add(LL tr[], int x, LL c)
21
{
22
    for (int i = x; i <= n; i += lowbit(i))
23
        tr[i] += c;
24
}
25

26
LL sum(LL tr[], int x)
27
{
28
    LL res = 0;
29

30
    for (int i = x; i; i -= lowbit(i))
31
        res += tr[i];
32

33
    return res;
34
}
35

36
LL prefix_sum(int x)
37
{
38
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
39
}
40

41
int main()
42
{
43
    cin >> n >> m;
44
    for (int i = 1; i <= n; i++)
45
        cin >> a[i];
46

47
    for (int i = 1; i <= n; i++)
48
    {
49
        int b = a[i] - a[i - 1];
50
        add(tr1, i, b);
51
        add(tr2, i, (LL) b * i);
52
    }
53

54
    while (m--)
55
    {
56
        char op;
57
        cin >> op;
58

59
        if (op == 'Q')
60
        {
61
            int l, r;
62
            cin >> l >> r;
63
            cout << prefix_sum(r) - prefix_sum(l - 1) << endl;
64
        }
65

66
        if (op == 'C')
67
        {
68
            int l, r, d;
69
            cin >> l >> r >> d;
70

71
            // a[l] += d
72
            add(tr1, l, d), add(tr2, l, l * d);
73

74
            // a[r + 1] -= d
75
            add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
76
        }
77
    }
78
    return 0;
79
}

应用-楼兰图腾#

思路#

思考这种问题时，可以从树状数组功能的角度思考：本题需要进行区间查询和单点修改两种操作，自然想到了使用树状数组

代码#

1
// Problem: 楼兰图腾
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/243/
4
// Time: 2026-02-26 20:14:56
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8
const int N = 200010;
9
typedef long long ll;
10

11
int n;
12
int a[N]; // 原数组
13
int tr[N]; // 树状数组
14
int Greater[N], lower[N]; // 用于存储某个位置左侧大于/小于它的数的个数，右侧的不用存，直接算就可以
15

16
int lowbit(int x)
17
{
18
    return x & -x;
19
}
20

21
void add(int x, int c)
22
{
23
    for (int i = x; i <= n; i += lowbit(i))
24
        tr[i] += c;
25
}
26

27
int sum(int x)
28
{
29
    int res = 0;
30
    for (int i = x; i; i -= lowbit(i))
31
        res += tr[i];
32

33
    return res;
34
}
35

36
int main()
37
{
38
    cin >> n;
39

40
    for (int i = 1; i <= n; i++)
41
        cin >> a[i];
42

43
    // 从左向右，依次统计每个位置左边比第i个数y小的数的个数、以及大的数的个数
44
    for (int i = 1; i <= n; i++)
45
    {
46
        int y = a[i];
47

48
        // 在前面已加入树状数组的所有数中统计在区间[y + 1, n]的数字的出现次数
49
        Greater[i] = sum(n) - sum(y);
50

51
        // 在前面已加入树状数组的所有数中统计在区间[1, y - 1]的数字的出现次数
52
        lower[i] = sum(y - 1);
53

54
        // 将y加入树状数组，即数字y在位置y出现1次
55
        add(y, 1);
56
    }
57

58
    // 清空树状数组，准备从右向左开始计算
59
    memset(tr, 0, sizeof tr);
60

61
    ll res1 = 0, res2 = 0;
62

63
    // 从右向左统计每个位置右边比第i个数y小的数的个数、以及大的数的个数
64
    for (int i = n; i; i--)
65
    {
66
        int y = a[i];
67

68
        res1 += Greater[i] * (ll) (sum(n) - sum(y));
69
        res2 += lower[i] * (ll) (sum(y - 1));
70

71
        add(y, 1);
72
    }
73

74
    cout << res1 << " " << res2 << endl;
75
    return 0;
76
}

逆序对问题#

P1908 逆序对 - 洛谷

由于我们只关注数字之间的相对大小关系，可以离散化。

在这个过程中，树状数组代表某个离散化后的值在当前遍历过程中出现的次数（频率）

统计逆序对的过程（从左到右遍历）：假设我们已经按原序列顺序从左向右遍历到了第 $i$ 个数 $a_i$ ，

此时我们一共遍历了 $i-1$ 个数。
我们查询树状数组中排名小于等于 $a_i$ 的数字出现的总次数（即 query(rank[a_i])）。
那么，在已经遍历过的数字中，严格大于 $a_i$ 的数字个数就是：(i - 1) - query(rank[a_i])。这部分数字都会与当前的 $a_i$ 构成逆序对。
统计完后，我们将 $a_i$ 的出现次数加 $1$ （即 add(rank[a_i], 1)），把它放入树状数组，继续遍历下一个。

1
// Problem: Luogu P1908
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P1908
4
// Time: 2026-05-17 16:17:34
5
// 使用树状数组维护在当前遍历过程中出现的次数
6
#include <bits/stdc++.h>
7
using namespace std;
8

9
// clang-format off
10
#define endl '\n'
11
#define all(x) (x).begin(), (x).end()
12
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
13
// clang-format on
14

15
using ll = long long;
16
using ull = unsigned long long;
17
using pii = pair<int, int>;
18
using pdd = pair<double, double>;
19
using pll = pair<long long, long long>;
20
using i128 = __int128;
21

22
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
23
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
24
const int inf = 0x3f3f3f3f;
25
const int N = 5e5 + 10;
26

27
int tr[N], a[N], n;
28
vector<int> b;
29

30
int lowbit(int x)
31
{
32
    return (x & -x);
33
}
34

35
void add(int i, ll k)
36
{
37
    for (; i <= n; i += lowbit(i))
38
        tr[i] += k;
39
}
40

41
ll query(int i)
42
{
43
    ll res = 0;
44
    for (; i > 0; i -= lowbit(i))
45
        res += tr[i];
46
    return res;
47
}
48

49
void solve()
50
{
51
    cin >> n;
52
    for (int i = 1; i <= n; i++)
53
    {
54
        cin >> a[i];
55
        b.push_back(a[i]);
56
    }
57

58
    sort(all(b));
59
    b.erase(unique(all(b)), b.end());
60

61
    ll res = 0;
62

63
    for (int i = 1; i <= n; i++)
64
    {
65
        int rank = lower_bound(all(b), a[i]) - b.begin() + 1;
66
        res += (i - 1) - query(rank);
67
        add(rank, 1);
68
    }
69

70
    cout << res << endl;
71
}
72

73
int main()
74
{
75
    fastio();
76

77
    int T = 1;
78
    // cin >> T;
79

80
    while (T--)
81
        solve();
82

83
    return 0;
84
}

线段树#

视频讲解：Bilibili 左程云

线段树概述#

线段树可以维护的信息类型：父范围上的某个信息，是可以用 $O(1)$ 的时间，从子范围的信息加工得到的。

例如：累加和，最大值，最小值是可以维护的；某范围上出现次数最多的数是不可以维护的。

举一个例子，假设我们要求一个数组所有元素的最大值，如果知道左半部分的最大值和右半部分的最大值，也就可以知道所有元素的最大值。

而“某范围上出现次数最多的数”这样的信息，是无法通过这种方式知道的，我们只能考察整个数组来计算。

线段树的经典功能是范围查询和范围修改。

范围查询：包括范围内累加和、最大值、最小值等信息。
范围修改：包括范围内每个数增加、重置等操作（如果这个修改功能可以通过 $O(1)$ 的时间计算出整体维护的信息，就可以实现 $O(\log n)$ 地单次调用）

例如：对 [5, 8] 这个区间的数整体都加上 5，可以直接算出来一共加了 20，而假如要对这个区间的数进行“逆序”，即 180 -> 81，就不能在 $O(1)$ 的时间内计算了，此时修改操作就不能是对数时间的。

建树与更新信息#

线段树的组织，以最经典的累加和举例

1，线段树开始下标可以为 1，也可以为 0，下标从 1 开始是最经典的设定

2，线段树需要在初始化时，就指定范围的规模 [1 ~ n]，一旦确定不能更改

3，任何一个大范围 [l ~ r]，严格从中点 mid，拆分成左范围 [l ~ mid]、右范围 [mid + 1 ~ r]

4，每个范围的信息，填写在独立的、连续数组 sum 中，最大的范围 [1 ~ n]，把信息填写在 sum[1]

5，如果父范围把信息填写在 sum[i]，那么左范围填写在sum[2 * i]，右范围填写在 sum[2 * i + 1]

6，范围 [l ~ r] 和 i 值的对应，是由公式限制死的，由递归参数维护，无需去记录对应关系

TIP
最好使用位运算，会更快！

Code#

根据上述的组织信息的原理，有线段树建树的模板（建树的时间复杂度为 $O(n)$ ）

1
void up(int u)
2
{
3
    sum[u] = sum[u << 1] + sum[u << 1 | 1]; // 某个节点的和就是左右两边的和相加
4
}
5

6
void build(int l, int r, int u) // 当前正在下标为 u 的点，这个点表示的区间是 [l, r]
7
{
8
    if (l == r)
9
        sum[u] = a[l];
10
    else
11
    {
12
        int mid = (l + r) >> 1;
13
        build(l, mid, u << 1); // u * 2
14
        build(mid + 1, r, u << 1 | 1); // u * 2 + 1
15
        up(u); // up的意义在于把某一个节点的信息通过它的子节点算出来
16
    }
17
}

有关空间：

线段树实际上是一棵某些位置空缺的满二叉树，对于任意的 n，这棵树的高度可能到达 $\log_2^n+2$ 层（考虑对数向上取整+1）。我们假设这棵树的高度为 h，由于它是一棵满二叉树，它的节点数量即为 $2^h-1$ 。将 $h=\log_2^n+2$ 代入节点数量，可以得到节点数量最大为 $4n-1$ ，又因为下标 0 不使用，所以综上所述，线段树的空间需要开到 4n。

范围查询#

我们从“下发”的角度从上到下考虑问题：

为什么线段树会更快？是因为它的基本思想是将一个总任务，下发到子节点作为子任务去处理。

比如说线段树支持维护原数组 1 - 64 位置上的信息，现在任务查询 10 - 55，它实际上经历了一个递归分治的过程。

当我们发现某个子区间是任务要求的真子集（例如图中 17 - 32 的情况），我们就没必要下发了，直接返回即可，这其实就是线段树速度快的原理。

这个操作的时间复杂度可以这样考虑：为了处理这个任务，一开始往两边分叉，中间会遇到很多“毛刺”，也就是下发给子节点处理的过程，但也很快就返回了，时间是可以忽略不计的，我们实际上就走了完整的一左一右两个区域（当然下面的部分是利用分治思想计算的），由于树的深度是对数的，因此这个操作的复杂度是 $O(\log n)$ 。

NOTE
查询操作时不需要 up()，查询时遇到懒信息同样需要下发，但由于是查询，不会实际更新到每个数上，因此不需要 up()

Code#

1
ll query(int jobl, int jobr, int l, int r, int u) // jobl 和 jobr 为任务的边界，永远不变
2
{
3
    if (jobl <= l && jobr >= r) // 遇到任务区间的真子集，直接返回
4
        return sum[u];
5

6
    int mid = (l + r) >> 1;
7
    down(u, mid - l + 1, r - mid);
8
    ll res = 0;
9

10
    if (jobl <= mid)
11
        res += query(jobl, jobr, l, mid, u << 1);
12

13
    if (jobr > mid)
14
        res += query(jobl, jobr, mid + 1, r, u << 1 | 1);
15

16
    return res;
17
}

范围增加——懒标记体系#

NOTE
对懒标记的理解：懒标记可以理解为修改标记，因为修改到的节点那么多，事实上以后用到的节点没有那么多。只有真正用到某一个节点的时候，才进行修改。如果一个点打上了一个懒标记，那么表示这个点的所有子节点都要变化这个懒标记。
注：如果是单点修改，直接捅到底，是不需要懒标记体系的。

原理与示例#

在线段树中实现范围增加，需要维护两个数组：

sum[] 用于维护对应区间的累加和
lazy_add[]（图中为 add[]）用于维护增加数量的懒信息

和范围查询的思想类似，假如我们要将 1 - 8 内所有的元素都 + 5（对应图片操作 1），这个任务区间全部命中了线段树中第一个元素所表示的区间，因此可以直接将 sum 值修改为 5 * 8 = 40，并在 add 数组中“懒”住这个信息，直到迫不得已时再去更新下面节点的信息。

假设我们现在要将 5 - 6 内所有的元素都 + 3（对应图片操作 2），此时应该首先处理上一个还在“懒”状态下的任务，把“懒信息”下发给下一层的子节点（懒标记遵循“能懒就懒”的原则，所以只下发一层），并把原来点上的任务清除（恢复不懒的状态），在下发的过程中更新 sum 的信息，直到上一个“懒”任务下发完成，我们执行当次的任务，并向上更新。

第三次操作类似于第二次操作，按照之前的思路进行更新即可。

NOTE
如果某天发现无法理解了，就回去看视频！

思路总结#

以最经典的范围内每个数字都增加来举例

数组与函数的定义：

sum数组 : 范围累加和(查询信息) add数组 : 范围上每个数的增加值(懒信息)

范围内每个数字都增加 : void add(jobl, jobr, jobv, l, r, u)

前三个是任务参数，表示 jobl ~ jobr 范围上，每个数增加 jobv，递归过程中这三个参数永远固定

后三个是范围参数，表示当前来到线段树的 l ~ r 范围上，信息存储位置是 u，递归过程中这三个参数可变

代码实现逻辑：

开始时调用 add(jobl, jobr, jobv, 1, n, 1)，范围增加的递归过程，懒更新机制！课上重点图解

如果发现任务范围 (jobl, jobr) 把当前范围 (l,r) 全覆盖了，不再向下传递任务，懒住！

lazy_add[i] += jobv; sum[i] += jobv * (r - l + 1);
如果任务范围不能把当前来到的范围全包，把该范围上积攒的懒信息，往下只下发一层（down 过程）

然后决定当前任务是否要去往左范围、右范围，继续调用子递归过程

子递归完成后，利用左右范围的 sum 信息，把当前范围的 sum[u] 信息修改正确（up 过程）
退出当前递归过程

Code#

1
// 懒信息的下发，u表示大范围的信息，ln表示左侧有多少个数，rn表示右侧有多少个数
2
void down(int u, int ln, int rn)
3
{
4
    if (lazy_add[u] != 0) // 当前不为0，表示有懒信息需要下发
5
    {
6
        lazy(u << 1, lazy_add[u], ln); // 下发给左侧
7
        lazy(u << 1, lazy_add[u], rn); // 下发给右侧
8
        lazy_add[u] = 0; // 在下发完成后，父亲的懒信息清空
9
    }
10
}
11

12
// 当前来到范围 l ~ r，对应的信息下标是 u，范围上数字的个数是 n = r - l + 1
13
// 现在收到一个懒更新任务：l ~ r 范围上每个数字增加 v，此时sum和add调整的方法，在lazy函数中实现
14
// 这个懒更新任务可能是任务范围把当前线段树范围全覆盖导致的，也可能是由父范围的懒信息下发下来的
15
void lazy(int u, ll v, int n)
16
{
17
    sum[i] += v * n;
18
    lazy_add[i] += v;
19
}
20

21
void add(int jobl, int jobr, ll jobv, int l, int r, int u)
22
{
23
    if (jobl <= l && jobr >= r)
24
        lazy(u, jobv, r - l + 1);
25
    else
26
    {
27
        int mid = (l + r) >> 1;
28
        down(u, mid - l + 1, r - mid); // 下发任务
29

30
        if (jobl <= mid)
31
            add(jobl, jobr, jobv, l, mid, u << 1);
32
        if (jobr > mid)
33
            add(jobl, jobr, jobv, mid + 1, r, u << 1 | 1);
34

35
        up(u);
36
    }
37
}

范围重置#

在线段树中实现范围重置，我们需要维护三个数组：

sum[]：维护对应区间的累加和
lazy_change[]：重置标记的值（Lazy Tag），记录当前区间被统一修改成了什么值
has_update[]：重置标记的开关（bool 值），记录当前区间是否存在还未下放的重置操作

NOTE
注意范围重置操作的懒标记有两个！
需要 has_update[] 这个数组的原因是：假如我们把某个区间重置成 0，那么 lazy_change[i] == 0，我们无法区分这里的 0 代表“有没有重置操作”还是“需要把区间内的所有数重置为 0”，因此必须再引入一个数组来作标记。

Code#

1
void up(int u)
2
{
3
    sum[u] = sum[u << 1] + sum[u << 1 | 1];
4
}
5

6
void lazy(int u, ll v, int n)
7
{
8
    sum[u] = v * n;
9
    lazy_change[u] = v;
10
    has_update[u] = true;
11
}
12

13
void down(int u, int ln, int rn)
14
{
15
    if (has_update[u])
16
    {
17
        lazy(u << 1, lazy_change[u], ln); // 标记下放给左孩子
18
        lazy(u << 1 | 1, lazy_change[u], rn); // 标记下放给右孩子
19
        has_update[u] = false; // 清空自身
20
    }
21
}
22

23
void update(int jobl, int jobr, ll jobv, int l, int r, int u)
24
{
25
    if (jobl <= l && jobr >= r) // 如果当前区间被完全包围，直接打懒标记
26
        lazy(u, jobv, r - l + 1);
27
    else
28
    {
29
        int mid = (l + r) >> 1;
30
        down(u, mid - l + 1, r - mid); // 去子树之前需要下放标记
31

32
        if (jobl <= mid)
33
            update(jobl, jobr, jobv, l, mid, u << 1);
34

35
        if (jobr > mid)
36
            update(jobl, jobr, jobv, mid + 1, r, u << 1 | 1);
37

38
        up(u); // 向上更新，重新计算sum
39
    }
40
}

query() 方法与前文相同。

范围增加 + 范围重置#

如果想同时实现这两个功能，需要处理懒标记的优先级问题，也就是我们该如何处理两种任务。

在线段树节点上，我们现在有两个懒标记：

重置标记 (lazy_change[] 和 has_update[])：代表“我这个区间要全部变成某个数”。
增加标记 (lazy_add[])：代表“我这个区间要在现有的基础上加上某个数”。

假如重置的时候前面有增加操作，这个增加操作就没有意义了：如果你昨天给区间加了 5，今天又给区间加了 3（此时 add = 8），但突然来了一个指令说“把区间重置为 10”。那么之前的 +8 就毫无意义了。

代码体现：在 updateLazy 中，必须有一句 lazy_add[i] = 0;。只要进行了重置，身上的加法标记立刻清零。

假如增加的时候前面有重置操作，这时两种操作互不影响，直接累加即可。

代码体现：addLazy 里只有 sum[i] += v * n; 和 lazy_add[i] += v;，不用管 update[] 数组。

既然一个节点身上可能同时存在重置标记和增加标记（比如先被重置为 10，然后又被加了 3），那么当下放标记给左右孩子时，应该先下放哪个？应该先下放“重置”，再下放“增加”。

代码体现：down 方法中，先写 if (update[i]) 的逻辑，后写 if (lazy_add[i] != 0) 的逻辑。顺序不能换！

完整代码#

范围修改+范围查询，维护累加和#

1
// Problem: Luogu P3372
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P3372
4
// Time: 2026-05-07 16:15:09
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
typedef long long ll;
15
typedef unsigned long long ull;
16
typedef pair<int, int> pii;
17
typedef pair<double, double> pdd;
18
typedef pair<long long, long long> pll;
19

20
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
21
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
22
const int inf = 0x3f3f3f3f;
23
const int N = 1e5 + 10;
24

25
ll sum[N << 2], info[N << 2], a[N];
26

27
void lazy(int u, ll v, int n)
28
{
29
    sum[u] += v * n;
30
    info[u] += v;
31
}
32

33
void up(int u)
34
{
35
    sum[u] = sum[u << 1] + sum[u << 1 | 1];
36
}
37

38
void down(int u, int ln, int rn)
39
{
40
    if (info[u] != 0)
41
    {
42
        lazy(u << 1, info[u], ln);
43
        lazy(u << 1 | 1, info[u], rn);
44
        info[u] = 0;
45
    }
46
}
47

48
void build(int l, int r, int u)
49
{
50
    if (l == r)
51
        sum[u] = a[l];
52
    else
53
    {
54
        int mid = (l + r) >> 1;
55
        build(l, mid, u << 1);
56
        build(mid + 1, r, u << 1 | 1);
57
        up(u);
58
    }
59
}
60

61
ll query(int jobl, int jobr, int l, int r, int u)
62
{
63
    if (jobl <= l && jobr >= r)
64
        return sum[u];
65

66
    int mid = (l + r) >> 1;
67
    down(u, mid - l + 1, r - mid);
68
    ll res = 0;
69

70
    if (jobl <= mid)
71
        res += query(jobl, jobr, l, mid, u << 1);
72

73
    if (jobr > mid)
74
        res += query(jobl, jobr, mid + 1, r, u << 1 | 1);
75

76
    return res;
77
}
78

79
void add(int jobl, int jobr, ll jobv, int l, int r, int u)
80
{
81
    if (jobl <= l && jobr >= r)
82
        lazy(u, jobv, r - l + 1);
83
    else
84
    {
85
        int mid = (l + r) >> 1;
86
        down(u, mid - l + 1, r - mid);
87

88
        if (jobl <= mid)
89
            add(jobl, jobr, jobv, l, mid, u << 1);
90
        if (jobr > mid)
91
            add(jobl, jobr, jobv, mid + 1, r, u << 1 | 1);
92

93
        up(u);
94
    }
95
}
96

97
void solve()
98
{
99
    int n, m;
100
    cin >> n >> m;
101

102
    for (int i = 1; i <= n; i++)
103
        cin >> a[i];
104

105
    build(1, n, 1);
106

107
    while (m--)
108
    {
109
        int op;
110
        cin >> op;
111

112
        if (op == 1)
113
        {
114
            int x, y;
115
            ll k;
116
            cin >> x >> y >> k;
117
            add(x, y, k, 1, n, 1);
118
        }
119
        else
120
        {
121
            int x, y;
122
            cin >> x >> y;
123
            cout << query(x, y, 1, n, 1) << endl;
124
        }
125
    }
126
}
127

128
int main()
129
{
130
    fastio();
131

132
    int T = 1;
133
    // cin >> T;
134

135
    while (T--)
136
        solve();
137

138
    return 0;
139
}

范围重置 + 范围增加 + 范围查询（维护最大值）#

1
// Problem: Luogu P1253
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P1253
4
// Time: 2026-05-07 19:43:59
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
typedef long long ll;
15
typedef unsigned long long ull;
16
typedef pair<int, int> pii;
17
typedef pair<double, double> pdd;
18
typedef pair<long long, long long> pll;
19

20
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
21
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
22
const ll inf = 1e18;
23
const int N = 1e6 + 1;
24

25
ll arr[N], tree_max[N << 2], lazy_add[N << 2], lazy_change[N << 2];
26
bool has_update[N << 2];
27

28
void up(int u)
29
{
30
    tree_max[u] = max(tree_max[u << 1], tree_max[u << 1 | 1]);
31
}
32

33
void updateLazy(int u, ll v)
34
{
35
    tree_max[u] = v;
36
    lazy_add[u] = 0;
37
    lazy_change[u] = v;
38
    has_update[u] = true;
39
}
40

41
void addLazy(int u, ll v)
42
{
43
    tree_max[u] += v;
44
    lazy_add[u] += v;
45
}
46

47
void down(int u)
48
{
49
    if (has_update[u])
50
    {
51
        updateLazy(u << 1, lazy_change[u]);
52
        updateLazy(u << 1 | 1, lazy_change[u]);
53
        has_update[u] = false;
54
    }
55
    if (lazy_add[u] != 0)
56
    {
57
        addLazy(u << 1, lazy_add[u]);
58
        addLazy(u << 1 | 1, lazy_add[u]);
59
        lazy_add[u] = 0;
60
    }
61
}
62

63
void build(int l, int r, int u)
64
{
65
    if (l == r)
66
        tree_max[u] = arr[l];
67
    else
68
    {
69
        int mid = (l + r) >> 1;
70
        build(l, mid, u << 1);
71
        build(mid + 1, r, u << 1 | 1);
72
        up(u);
73
    }
74

75
    lazy_add[u] = 0;
76
    lazy_change[u] = 0;
77
    has_update[u] = false;
78
}
79

80
void update_tree(int jobl, int jobr, ll jobv, int l, int r, int u)
81
{
82
    if (jobl <= l && jobr >= r)
83
        updateLazy(u, jobv);
84
    else
85
    {
86
        int mid = (l + r) >> 1;
87

88
        down(u);
89
        if (jobl <= mid)
90
            update_tree(jobl, jobr, jobv, l, mid, u << 1);
91
        if (jobr > mid)
92
            update_tree(jobl, jobr, jobv, mid + 1, r, u << 1 | 1);
93

94
        up(u);
95
    }
96
}
97

98
void add_tree(int jobl, int jobr, ll jobv, int l, int r, int u)
99
{
100
    if (jobl <= l && jobr >= r)
101
        addLazy(u, jobv);
102
    else
103
    {
104
        int mid = (l + r) >> 1;
105

106
        down(u);
107
        if (jobl <= mid)
108
            add_tree(jobl, jobr, jobv, l, mid, u << 1);
109
        if (jobr > mid)
110
            add_tree(jobl, jobr, jobv, mid + 1, r, u << 1 | 1);
111

112
        up(u);
113
    }
114
}
115

116
ll query_tree(int jobl, int jobr, int l, int r, int u)
117
{
118
    if (jobl <= l && jobr >= r)
119
        return tree_max[u];
120

121
    int mid = (l + r) >> 1;
122
    down(u);
123

124
    ll res = -inf;
125
    if (jobl <= mid)
126
        res = max(res, query_tree(jobl, jobr, l, mid, u << 1));
127
    if (jobr > mid)
128
        res = max(res, query_tree(jobl, jobr, mid + 1, r, u << 1 | 1));
129

130
    return res;
131
}
132

133
void solve()
134
{
135
    int n, m;
136
    cin >> n >> m;
137

138
    for (int i = 1; i <= n; i++)
139
        cin >> arr[i];
140

141
    build(1, n, 1);
142

143
    while (m--)
144
    {
145
        int op, jobl, jobr;
146
        ll jobv;
147
        cin >> op >> jobl >> jobr;
148

149
        if (op == 1)
150
        {
151
            cin >> jobv;
152
            update_tree(jobl, jobr, jobv, 1, n, 1);
153
        }
154
        else if (op == 2)
155
        {
156
            cin >> jobv;
157
            add_tree(jobl, jobr, jobv, 1, n, 1);
158
        }
159
        else
160
            cout << query_tree(jobl, jobr, 1, n, 1) << endl;
161
    }
162
}
163

164
int main()
165
{
166
    fastio();
167

168
    int T = 1;
169
    // cin >> T;
170

171
    while (T--)
172
        solve();
173

174
    return 0;
175
}