线段树

简介

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在 $O (log N)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

线段树将每个长度不为1的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

过程

有个大小为 $5$ 的数组 $a=[10,11,12,13,14]$ ，要将其转化为线段树，有以下做法：设线段树的根节点编号为 $1$ ，用数组 $d$ 来保存我们的线段树，$d_i$ 用来保存线段树上编号为 $i$ 的节点的值，这里每个节点所维护的值就是这个节点所表示的区间总和。如图所示:

1

实现代码：

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
int n, m;
int a[100005] = {0};

struct node
{
    long long v, add;
} st[400007];

void build(int root, int l, int r)
{
    // 初始化lazytag
    st[root].add = 0;
    if (l == r)
    {
        st[root].v = a[l];
    }
    else
    {
        int m = (l + r) / 2;
        build(root * 2, l, m);
        build(root * 2 + 1, m + 1, r);
        st[root].v = st[root * 2].v + st[root * 2 + 1].v;
    }
    return;
}

关于线段树的空间:如果采用堆式存储（ $2p$ 是 $p$ 的左儿子，$2p+1$ 是 $p$ 的右儿子），若有几个叶
子结点，则 $d$ 数组的范围最大为 $2^{\lceil logn \rceil+1}$ 。

分析：容易知道线段树的深度是 $\lceil logn \rceil$ 的，则在堆式储存情况下叶子节点（包括无用的叶子节点）数量为 $2^{\lceil logn \rceil}$ 个，又由于其为一棵完全二叉树，则其总节点个数 $2^{\lceil logn \rceil+1}-1$ 。当然如果你懒得计算的话可以直接把数组长度设为 $4n$，因为 $\frac {2^{\lceil logn \rceil+1}-1}{n}$ 的最大值在 $n= 2^x+1 \ (x∈ N_+)$ 时取到，此时节点数为 $2^{\lceil logn \rceil+1}-1=2^{x+2}-1=4n-5$ 。

而堆式存储存在无用的叶子节点，可以考虑使用内存池管理线段树节点，每当需要新建节点时从池中获取。自底向上考虑，必有每两个底层节点合并为一个上层节点，因此可以类似哈夫曼树地证明，如果有 $n$ 个叶子节点，这样的线段树总共有 $2n-1$ 个节点。其空间效率优于堆式存储，并且是可能的最优情况。

区间修改懒惰标记

如果要求修改区间 $[l,r]$ ，把所有包含在区间 $[l,r]$ 中的节点都遍历一次、修改一次，时间复杂度无
法承受。我们这里要引入一个叫做懒惰标记的东西。

懒惰标记，简单来说，就是通过延迟对节点信息的更改，从而减少可能不必要的操作次数。每次执行修改时，我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。仍然以最开始的图为例，我们将执行若干次给区间内的数加上一个值的操作。我们现在给每个节点增加一个t，表示该节点带的标记值。
最开始时的情况是这样的：

2

现在我们准备给[3,5]上的每个数都加上 5。根据前面区间查询的经验，我们很快找到了两个极大区间 $[3,3]$ 和 $[4,5]$ 。我们直接在这两个节点上进行修改，并给它们打上标记。

3

我们发现，3号节点的信息虽然被修改了（因为该区间管辖两个数，所以 $d$ 加上的数是 $5*2=10$），但它的两个子节点却还没更新，仍然保留着修改之前的信息。虽然修改目前还没进行，但当我们要查询这两个子节点的信息时，我们会利用标记修改这两个子节点的信息，使查询的结果依旧准确。

接下来我们查询一下 $[4,4]$ 区间上各数字的和。

我们通过递归找到 $[4,5]$ 区间，发现该区间并非我们的目标区间，且该区间上还存在标记。这时候
就到标记下放的时间了。我们将该区间的两个子区间的信息更新，并清除该区间上的标记。

4

现在 6、7两个节点的值变成了最新的值，查询的结果也是准确的。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
// 核心代码，维护lazytag
void pushdown(int root, int l, int r)
{
    int m = (l + r) / 2;
    st[root * 2].v += st[root].add * (m - l + 1);
    st[root * 2 + 1].v += st[root].add * (r - m);
    st[root * 2].add += st[root].add;
    st[root * 2 + 1].add += st[root].add;
    // 把父节点的值初始化
    st[root].add = 0;
    return;
}

区间查询

一般地，如果要查询的区间是 $[l,r]$，则可以将其拆成最多为 $O(log \ n)$ 个 极大 的区间，合并这些区
间即可求出 $[l,r]$ 的答案。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll query(int root, int stdl, int stdr, int l, int r)
{
    if (r < stdl || stdr < l)
    {
        return 0;
    }
    if (l <= stdl && stdr <= r)
    {
        return st[root].v;
    }
    pushdown(root, stdl, stdr);
    int m = (stdl + stdr) / 2;
    return query(root * 2, stdl, m, l, r) + query(root * 2 + 1, m + 1, stdr, l, r);
}

动态开点线段树

前面讲到堆式储存的情况下，需要给线段树开 $4n$ 大小的数组。为了节省空间，我们可以不一次性建好树，而是在最初只建立一个根结点代表整个区间。当我们需要访问某个子区间时，才建立代表这个区间的子结点。这样我们不再使用 $2p$ 和 $2p+1$ 代表 $p$ 结点的儿子，而是用 $ls$ 和 $rs$ 记录儿子的编号。总之，动态开点线段树的核心思想就是：结点只有在有需要的时候才被创建。

单次操作的时间复杂度是不变的，为 $O(log\ n)$。由于每次操作都有可能创建并访问全新的一系列结点，因此 m 次单点操作后结点的数量规模是 $O(m\ log\ n)$ 。最多也只需要 $2n-1$ 个结点，没有浪费。

单点修改

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

// root 表示整棵线段树的根结点；cnt 表示当前结点个数
int n, cnt, root;
int sum[n * 2], ls[n * 2], rs[n * 2];

// 用法：update(root, 1, n, x, f); 其中 x 为待修改节点的编号
void update(int &p, int s, int t, int x, int f)
{   
    // 引用传参
    if (!p) // 当结点为空时，创建一个新的结点
    {
        p = ++cnt;
    }
    if (s == t)
    {
        sum[p] += f;
        return;
    }
    int m = s + ((t - s) >> 1);
    if (x <= m)
    {
        update(ls[p], s, m, x, f);
    }
    else
    {
        update(rs[p], m + 1, t, x, f);
    }
    sum[p] = sum[ls[p]] + sum[rs[p]]; // pushup
}

区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 用法：query(root, 1, n, l, r);
int query(int p, int s, int t, int l, int r)
{
    if (!p) // 如果结点为空，返回 0
    {
        return 0;
    }
    if (s >= l && t <= r)
    {
        return sum[p];
    }
    int m = s + ((t - s) >> 1), ans = 0;
    if (l <= m)
    {
        ans += query(ls[p], s, m, l, r);
    }
    if (r > m)
    {
        ans += query(rs[p], m + 1, t, l, r);
    }
    return ans;
}

区间修改也是一样的，不过下放标记时要注意如果缺少孩子，就直接创建一个新的孩子。或者使用标记永久化技巧。

一些优化

这里总结几个线段树的优化：

  • 在叶子节点处无需下放懒惰标记，所以懒惰标记可以不下传到叶子节点。
  • 下放懒惰标记可以写一个专门的函数 pushdown，从儿子节点更新当前节点也可以写一个专门的函数 maintain（或者对称地用 pushup），降低代码编写难度。
  • 标记永久化：如果确定懒惰标记不会在中途被加到溢出（即超过了该类型数据所能表示的最大范围），那么就可以将标记永久化。标记永久化可以避免下传懒惰标记，只需在进行询问时把标记的影响加到答案当中，从而降低程序常数。具体如何处理与题目特性相关，需结合题目来写。这也是树套树和可持久化数据结构中会用到的一种技巧。

模板例题

【模板】线段树 1 - 洛谷

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef long double ld;

int n, m;
int a[100005] = {0};

struct node
{
    long long v, add;
} st[400007];

// 核心代码，维护lazytag
void pushdown(int root, int l, int r)
{
    int m = (l + r) / 2;
    st[root * 2].v += st[root].add * (m - l + 1);
    st[root * 2 + 1].v += st[root].add * (r - m);
    st[root * 2].add += st[root].add;
    st[root * 2 + 1].add += st[root].add;
    // 把父节点的值初始化
    st[root].add = 0;
    return;
}

void build(int root, int l, int r)
{
    // 初始化lazytag
    st[root].add = 0;
    if (l == r)
    {
        st[root].v = a[l];
    }
    else
    {
        int m = (l + r) / 2;
        build(root * 2, l, m);
        build(root * 2 + 1, m + 1, r);
        st[root].v = st[root * 2].v + st[root * 2 + 1].v;
    }
    return;
}

// 核心是找到最大能覆盖住l，r的子区间进行更改和标记
//  stdl，stdr为root管辖的区间
void updatesum(int root, int stdl, int stdr, int l, int r, ll k)
{
    if (r < stdl || stdr < l)
    {
        return;
    }
    // 如果能覆盖住，直接更新，子区间的以后在更改（懒标记）
    if (l <= stdl && stdr <= r)
    {
        st[root].add = st[root].add + k;
        st[root].v = st[root].v + k * (stdr - stdl + 1);
        return;
    }
    // 先下放以前的父节点的更新
    pushdown(root, stdl, stdr);
    int m = (stdl + stdr) / 2;
    updatesum(root * 2, stdl, m, l, r, k);
    updatesum(root * 2 + 1, m + 1, stdr, l, r, k);
    st[root].v = st[root * 2].v + st[root * 2 + 1].v;
    return;
}

ll query(int root, int stdl, int stdr, int l, int r)
{
    if (r < stdl || stdr < l)
    {
        return 0;
    }
    if (l <= stdl && stdr <= r)
    {
        return st[root].v;
    }
    pushdown(root, stdl, stdr);
    int m = (stdl + stdr) / 2;
    return query(root * 2, stdl, m, l, r) + query(root * 2 + 1, m + 1, stdr, l, r);
}

void debug()
{
    for (int i = 1; i <= 10; i++)
    {
        cout << st[i].v << " ";
    }
    cout << endl;
    return;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    build(1, 1, n);
    // debug();
    int op;
    int x, y, k;
    for (int i = 1; i <= m; i++)
    {
        cin >> op >> x >> y;
        if (op == 1)
        {
            cin >> k;
            updatesum(1, 1, n, x, y, k);
        }
        else if (op == 2)
        {
            cout << query(1, 1, n, x, y) << endl;
            // debug();
        }
    }
    return;
}

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

    int t;
    t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

【模板】线段树 2 - 洛谷

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef long double ld;

int n, m, p;
ll a[100005] = {0};

struct node
{
    long long v, mul, add;
} st[400007];
// 核心代码，维护lazytag
void pushdown(int root, int l, int r)
{
    int m = (l + r) / 2;
    // 儿子的值=此刻儿子的值*爸爸的乘法lazytag+儿子的区间长度*爸爸的加法lazytag
    st[root * 2].v = (st[root * 2].v * st[root].mul + st[root].add * (m - l + 1)) % p;
    st[root * 2 + 1].v = (st[root * 2 + 1].v * st[root].mul + st[root].add * (r - m)) % p;
    // 很好维护的lazytag
    st[root * 2].mul = (st[root * 2].mul * st[root].mul) % p;
    st[root * 2 + 1].mul = (st[root * 2 + 1].mul * st[root].mul) % p;
    st[root * 2].add = (st[root * 2].add * st[root].mul + st[root].add) % p;
    st[root * 2 + 1].add = (st[root * 2 + 1].add * st[root].mul + st[root].add) % p;
    // 把父节点的值初始化
    st[root].mul = 1;
    st[root].add = 0;
    return;
}
void build(int root, int l, int r)
{
    // 初始化lazytag
    st[root].mul = 1;
    st[root].add = 0;
    if (l == r)
    {
        st[root].v = a[l];
    }
    else
    {
        int m = (l + r) / 2;
        build(root * 2, l, m);
        build(root * 2 + 1, m + 1, r);
        st[root].v = st[root * 2].v + st[root * 2 + 1].v;
    }
    st[root].v %= p;
    return;
}
void updatemul(int root, int stdl, int stdr, int l, int r, ll k)
{
    if (r < stdl || stdr < l)
    {
        return;
    }
    if (l <= stdl && stdr <= r)
    {
        st[root].v = (st[root].v * k) % p;
        st[root].mul = (st[root].mul * k) % p;
        st[root].add = (st[root].add * k) % p;
        return;
    }
    // 假如给出的区间和本区间有交集，但是也有不交叉的部分
    // 先传递lazytag
    pushdown(root, stdl, stdr);
    int m = (stdl + stdr) / 2;
    updatemul(root * 2, stdl, m, l, r, k);
    updatemul(root * 2 + 1, m + 1, stdr, l, r, k);
    st[root].v = (st[root * 2].v + st[root * 2 + 1].v) % p;
    return;
}
void updatesum(int root, int stdl, int stdr, int l, int r, ll k)
{
    if (r < stdl || stdr < l)
    {
        return;
    }
    if (l <= stdl && stdr <= r)
    {
        st[root].add = (st[root].add + k) % p;
        st[root].v = (st[root].v + k * (stdr - stdl + 1)) % p;
        return;
    }
    pushdown(root, stdl, stdr);
    int m = (stdl + stdr) / 2;
    updatesum(root * 2, stdl, m, l, r, k);
    updatesum(root * 2 + 1, m + 1, stdr, l, r, k);
    st[root].v = (st[root * 2].v + st[root * 2 + 1].v) % p;
    return;
}
ll query(int root, int stdl, int stdr, int l, int r)
{
    if (r < stdl || stdr < l)
    {
        return 0;
    }
    if (l <= stdl && stdr <= r)
    {
        return st[root].v;
    }
    pushdown(root, stdl, stdr);
    int m = (stdl + stdr) / 2;
    return (query(root * 2, stdl, m, l, r) + query(root * 2 + 1, m + 1, stdr, l, r)) % p;
}
void solve()
{
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    build(1, 1, n);
    int op;
    int x, y, k;
    for (int i = 1; i <= m; i++)
    {
        cin >> op >> x >> y;
        if (op == 1)
        {
            cin >> k;
            updatemul(1, 1, n, x, y, k);
        }
        else if (op == 2)
        {
            cin >> k;
            updatesum(1, 1, n, x, y, k);
        }
        else
        {
            cout << query(1, 1, n, x, y) << endl;
        }
    }
    return;
}

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

    int t;
    t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
算法
#算法
线段树
https://serendipity565.github.io/posts/51668695af7a/
作者
Serendipity
发布于
2024年7月26日
许可协议
BY-SERENDIPITY565