线段树

发表于 更新于 分类于 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 9 分钟

原题：https://www.luogu.com.cn/problem/P3372
教程：https://oi-wiki.org/ds/seg/

【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上 。
  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 ，分别表示该数列数字的个数和操作的总个数。

第二行包含 个用空格分隔的整数，其中第 个数字表示数列第 项的初始值。

接下来 行每行包含 或 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 内每个数加上 。
  2. 2 x y：输出区间 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

样例输出 #1

1
2
3
11
8
20

提示

对于 的数据：，。
对于 的数据：，。
对于 的数据：。

保证任意时刻数列中所有元素的绝对值之和 。

【样例解释】

线段树的结构

这个数据结构，可以高效地对区间进行更新和查询

alt text

1
2
3
int t[N];      // 线段树的值（和）
int a[N];      // 原始数组
int lazy[N];   // 懒惰标记

线段树的建立

alt text

对一整个区间和，递归，对半分成两个区间和，直到区间长度为1为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
build(1, n, 1); //开始建树

// 构造函数：初始化原始数组，构建线段树
void build(int l, int r, int p) {
    if (l == r) {//区间长度为1
        t[p] = a[l];
        return;
    }
    int mid = l + ((r - l) >> 1);  //中分mid=(l+r)/2
    int lc = (p << 1), rc = lc | 1;//左子树lc=p*2,右子树rc=lc+1
    build(l, mid, lc);             //左递归建树
    build(mid + 1, r, rc);         //右递归建树
    t[p] = t[lc] + t[rc];          //求和
}

线段树的更新

懒惰标记

没必要每次更新，都把每个点修改。而是引入一个懒惰标记。
每当访问到一个节点时，如果它有懒惰标记，就会先更新该节点和其子节点，然后清空该节点的懒惰标记。
懒惰标记表示，此区间的子区间都还欠着多少没加。

(点击标题进来看就有图片了)
操作前
(首页看排版应该是乱的)
[2,4]区间内所有数加2
(所以点击标题喵)
[3,4]区间内所有数加1 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 区间加法操作,对区间[l,r]加上c
void add(int l, int r, int i, int j, int p, int c) {
    if (l <= i && j <= r) {     //[i,j]在更新区间[l,r]里
        t[p] += (j - i + 1) * c;//该区间[i,j]更新求和
        lazy[p] += c;           //懒惰标记，先不往子树更新，等下一次操作再说
        return;
    }
    int mid = i + ((j - i) >> 1); //中分mid=(l+r)/2
    int lc = (p << 1), rc = lc | 1;//左子树lc=p*2,右子树rc=lc+1
    if (lazy[p] && i != j) {             //已经有懒惰标记，而且长度大于1
        t[lc] += lazy[p] * (mid - i + 1);//左子树更新和
        t[rc] += lazy[p] * (j - mid);//右子树更新和
        lazy[lc] += lazy[p];//左子树更新懒惰标记
        lazy[rc] += lazy[p];//右子树更新懒惰标记
        lazy[p] = 0;//清除懒惰标记
    }
    if (l <= mid) add(l, r, i, mid, lc, c);   //左子树递归更新
    if (mid < r) add(l, r, mid + 1, j, rc, c);//右子树递归更新
    t[p] = t[lc] + t[rc];
}

线段树的求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 区间求和操作，求[l,r]的和
int getsum(int l, int r, int i, int j, int p) {
    if (l <= i && j <= r) return t[p];//[i,j]在[l,r]里，直接查询
    int mid = i + ((j - i) >> 1);     //中分mid=(l+r)/2
    int lc = (p << 1), rc = lc | 1;   //左子树lc=p*2,右子树rc=lc+1
    if (lazy[p]) {                       //有未更新的懒惰标记
        t[lc] += lazy[p] * (mid - i + 1);//左子树更新和
        t[rc] += lazy[p] * (j - mid);    //右子树更新和
        lazy[lc] += lazy[p];             //左子树更新懒惰标记
        lazy[rc] += lazy[p];             //右子树更新懒惰标记
    }
    lazy[p] = 0;//清除懒惰标记
    int sum = 0;
    if (l <= mid) sum = getsum(l, r, i, mid, lc);//左子树递归求和
    if (mid < r) sum += getsum(l, r, mid + 1, j, rc);//右子树递归求和
    return sum;
}

流程图

建立 更新 查询
递归出口 if 区间长度为1 if 窗口[i,j]包含于更新区间[l,r]里
t[p] = a[l] 更新当前区间和，加懒惰标志 返回当前区间和
设分界点 中分mid
左子树的索引 lc
右子树的索引 rc
分支判断 无 if 有懒惰 并且 长度不为1 if 只有懒惰
左、右子树更新和、懒惰标记
无 清除当前区间的懒惰标记
递归左右子树 无判断递归 判断区间是否越界：l <= mid < r

总代码

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
#include <bits/stdc++.h>
using namespace std;
#define N 400005
#define int long long

int t[N];      // 线段树的值（和）
int a[N];      // 原始数组
int lazy[N];   // 懒惰标记

// 构造函数：初始化原始数组，构建线段树
void build(int l, int r, int p) {
    if (l == r) {//区间长度为1
        t[p] = a[l];
        return;
    }
    int mid = l + ((r - l) >> 1);  //中分mid=(l+r)/2
    int lc = (p << 1), rc = lc | 1;//左子树lc=p*2,右子树rc=lc+1
    build(l, mid, lc);             //左递归建树
    build(mid + 1, r, rc);         //右递归建树
    t[p] = t[lc] + t[rc];          //求和
}

void init(int n) {
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, n, 1);  // 构建线段树
}

// 区间加法操作,对区间[l,r]加上c
void add(int l, int r, int i, int j, int p, int c) {
    if (l <= i && j <= r) {     //[i,j]在更新区间[l,r]里
        t[p] += (j - i + 1) * c;//该区间[i,j]更新求和
        lazy[p] += c;           //懒惰标记，先不往子树更新，等下一次操作再说
        return;
    }
    int mid = i + ((j - i) >> 1); //中分mid=(l+r)/2
    int lc = (p << 1), rc = lc | 1;//左子树lc=p*2,右子树rc=lc+1
    if (lazy[p] && i != j) {             //已经有懒惰标记，而且长度大于1
        t[lc] += lazy[p] * (mid - i + 1);//左子树更新和
        t[rc] += lazy[p] * (j - mid);//右子树更新和
        lazy[lc] += lazy[p];//左子树更新懒惰标记
        lazy[rc] += lazy[p];//右子树更新懒惰标记
        lazy[p] = 0;//清除懒惰标记
    }
    if (l <= mid) add(l, r, i, mid, lc, c);   //左子树递归更新
    if (mid < r) add(l, r, mid + 1, j, rc, c);//右子树递归更新
    t[p] = t[lc] + t[rc];
}

// 区间求和操作，求[l,r]的和
int getsum(int l, int r, int i, int j, int p) {
    if (l <= i && j <= r) return t[p];//[i,j]在[l,r]里，直接查询
    int mid = i + ((j - i) >> 1);     //中分mid=(l+r)/2
    int lc = (p << 1), rc = lc | 1;   //左子树lc=p*2,右子树rc=lc+1
    if (lazy[p]) {                       //有未更新的懒惰标记
        t[lc] += lazy[p] * (mid - i + 1);//左子树更新和
        t[rc] += lazy[p] * (j - mid);    //右子树更新和
        lazy[lc] += lazy[p];             //左子树更新懒惰标记
        lazy[rc] += lazy[p];             //右子树更新懒惰标记
    }
    lazy[p] = 0;//清除懒惰标记
    int sum = 0;
    if (l <= mid) sum = getsum(l, r, i, mid, lc);//左子树递归求和
    if (mid < r) sum += getsum(l, r, mid + 1, j, rc);//右子树递归求和
    return sum;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m, x, y, cmd, k;
    cin >> n >> m;
    // 创建并初始化线段树
    init(n);
    // 处理操作
    while (m--) {
        cin >> cmd;
        if (cmd == 1) {
            cin >> x >> y >> k;
            add(x, y, 1, n, 1, k);  // 对区间 [x, y] 加上 k
        } else {
            cin >> x >> y;
            cout << getsum(x, y, 1, n, 1) << endl;  // 查询区间 [x, y] 的和
        }
    }
    return 0;
}

【模板】线段树 2

带乘法和加法

https://www.luogu.com.cn/problem/P3373

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 4e5 + 5;
using ll = long long;
#define int long long
int n, m, q, t[M], a[N], lazy1[M], lazy2[M];//乘法、加法懒标记
void build(int l, int r, int p)
{
    lazy1[p]=1;
    if (l == r)
    {
        t[p] = a[l] % m;
        return;
    }
    int mid = l + ((r - l) >> 1), lc = p << 1, rc = lc | 1;
    build(l, mid, lc);
    build(mid + 1, r, rc);
    t[p] = (t[lc] + t[rc]) % m;
}
inline void update(int i,int j,int p,int mid,int lc,int rc)
{
    t[lc] = (t[lc] * lazy1[p] % m + lazy2[p] * (mid - i + 1) % m) % m; // 算出来
    t[rc] = (t[rc] * lazy1[p] % m + lazy2[p] * (j - mid) % m) % m;
    lazy1[lc] = lazy1[lc] * lazy1[p] % m;
    lazy1[rc] = lazy1[rc] * lazy1[p] % m;
    lazy2[lc] = (lazy2[lc] * lazy1[p] % m + lazy2[p]) % m;
    lazy2[rc] = (lazy2[rc] * lazy1[p] % m + lazy2[p]) % m;
    lazy1[p] = 1;
    lazy2[p] = 0;
}
void add(int l, int r, int i, int j, int p, int k)
{
    if (l <= i && j <= r)
    {
        t[p] = (t[p] + (j - i + 1) * k % m) % m;
        lazy2[p] = (lazy2[p] + k) % m;
        return;
    }
    int mid = i + ((j - i) >> 1), lc = p << 1, rc = lc | 1;
    update(i,j,p,mid,lc,rc);
    if (l <= mid)
        add(l, r, i, mid, lc, k);
    if (mid < r)
        add(l, r, mid + 1, j, rc, k);
    t[p] = (t[lc] + t[rc]) % m;
}
void mul(int l, int r, int i, int j, int p, int k)
{
    if (l <= i && j <= r)
    {
        t[p] = t[p] * k % m;
        lazy1[p] = lazy1[p] * k % m;
        lazy2[p] = lazy2[p] * k % m;
        return;
    }
    int mid = i + ((j - i) >> 1), lc = p << 1, rc = lc | 1;
    update(i,j,p,mid,lc,rc);
    if (l <= mid)
        mul(l, r, i, mid, lc, k);
    if (mid < r)
        mul(l, r, mid + 1, j, rc, k);
    t[p] = (t[lc] + t[rc]) % m;
}
int getsum(int l, int r, int i, int j, int p)
{
    if (l <= i && j <= r)
    {
        return t[p];
    }
    int mid = i + ((j - i) >> 1), lc = p << 1, rc = lc | 1;
    update(i,j,p,mid,lc,rc);
    int sum = 0;
    if (l <= mid)
        sum = getsum(l, r, i, mid, lc);
    if (mid < r)
        sum += getsum(l, r, mid + 1, j, rc);
    return sum % m;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> q >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, n, 1);
    int cmd, l, r, k;
    while (q--)
    {
        cin >> cmd;
        switch (cmd)
        {
        case 1:
            cin >> l >> r >> k;
            mul(l, r, 1, n, 1, k % m);
            break;
        case 2:
            cin >> l >> r >> k;
            add(l, r, 1, n, 1, k % m);
            break;
        default:
            cin >> l >> r;
            cout << getsum(l, r, 1, n, 1) << endl;
            break;
        }
    }
    return 0;
}