跳转至

线段树

简介

树状数组通过精细的二进制拆分，将任何一个前缀变成了 \(\mathcal{O}(\log n)\) 个信息的拼接，同时利用所维护信息的可减性，将任意一个区间变作两个前缀的差，从而快速地维护出了区间信息。

注意树状数组维护内容的限制条件：假如询问的是区间而非前缀，那么我们维护的信息必须要有可减性：因为我们要将其表示为两个区间的差。

于是我们想：有没有一种更加强大的数据结构，使得我们可以不关注信息是否可减而直接得出区间结果呢？非常幸运，这样的数据结构存在且并不困难，它就叫线段树。

线段树的结构

仿照树状数组的思路，我们希望能够将任何一个区间拆分成 \(\mathcal{O}(\log n)\) 个小区间，并且在修改时快速维护这些小区间的变化，合并信息得到询问区间的答案。

不妨设我们要维护的区间是 \([1,n]\)，采取一种更为暴力的拆分方式：初始结点代表区间 \([1,n]\) 的信息，在这之后每个结点会生成两个新结点，称为它的子结点。代表区间 \([l,r]\) 的信息的区间的左子结点代表区间 \([l,\lfloor\frac{l+r}{2}\rfloor]\)，右子结点代表区间 \([\lfloor\frac{l+r}{2}\rfloor+1,r]\)，特别地，代表区间 \([x,x]\) 这一个元素的结点没有子结点。每个结点的子结点本质上将 \([l,r]\) 几乎均分为了两份。（“几乎”是因为取整符号）

例如区间 \([1,7]\) 的子结点代表区间 \([1,4]\) 和 \([5,7]\)，\([1,4]\) 的子结点代表区间 \([1,2]\) 和 \([3,4]\)，\([5,7]\) 的子结点代表区间 \([5,6]\) 和 \([7,7]\)，\([1,2]\)，\([3,4]\)，\([5,6]\) 的子结点分别为 \([1,1]\) 和 \([2,2]\)、\([3,3]\) 和 \([4,4]\)、\([5,5]\) 和 \([6,6]\)，可以用下图的树状结构来描述一棵线段树：

待补充

填坑中

操作过程

线段树是一种树型结构 ， 我们可以在每个节点存对应区间的值(如和 ，最大最小值等) 。

1号节点对应根节点 ， 然后不断往 左右递归求解（下图来自oi-wiki）

每个节点对应其所管辖区间的值 ， 只需要在递归到叶子结点的时候上传即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void maintain(int u){// pushup 上传的函数
    T[u] = T[lc] + T[rc];
}

void Build(int u , int l , int r){
    if(l == r){ // 到叶子节点了
        T[u] = A[l];// A为给定数组的值
         return;
    }
    int mid = (l + r) >> 1;
    Build(u << 1 , l , mid);
    Build(u << 1 | 1 , mid + 1 , r);
    maintain(u);
}

因为本树高度为 logn ， 所以总节点数量为 2 ^ log n ， 大概为4n ， 所以 T数组（节点信息）需要开4 * N。

区间查询

从根节点开始 ， 不断找需要查询的区间， 跟二分差不多。

需要查询的区间在当前递归的区间的左半边，就递归左半边 ， 反之则递归右半边

不然左右都进行递归（代码后面给）

单点，区间修改 懒标记

单点修改与区间修改区别不大，也可包含进区间修改，故不做细说

以区间加法为例，区间里面一个一个加这样太慢了

我们需要维护一个懒标记 ， 懒标记存的是当前区间每个数需要加的数。

我们不用加一次 把整棵树修改一下，因为有些区间我们根本不用一直往下递归，能直接返回这个区间的值

所以这就是我们维护懒标记的意义。

当我们需要往下递归的时候 ， 把懒标记也下放到左右区间，这个节点懒标记清零，这里就需要一个下方的操作

（代码后面给）

实现

例题

P3372 【模板】线段树 1

P3373 【模板】线段树 2

线段树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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int A[N] , n , m;

namespace SegmentTree{ // (hyoi习惯，开命名空间)  把线段树的相关操作打包 好看而已
#define lc (u << 1) // 定义u 左子树为 lc
#define rc (u << 1 | 1) // 定义u 右子树为 rc
#define mid ((l + r) >> 1) // 定义mid  （这样写方便，每次定义也没有影响）
    int T[N << 2] , tag[N << 2];

    inline void maintain(int u) { //上传的函数
        T[u] = T[lc] + T[rc];
    }
    inline void Tag(int u , int l , int r , int x){ //对某段区间加x
        T[u] += (r - l + 1) * x;// 区间和 加 区间长度 * 每个数加的数
        tag[u] += x ;// 懒标记记录
    }
    inline void pushdown(int u , int l , int r){// 下放 
        Tag(lc , l , mid , tag[u]);// 左边下放 加上
        Tag(rc , mid + 1 , r , tag[u]); // 右边下放 加上
        tag[u] = 0;//把本区间懒标记清空
    }

    inline void Build(int u , int l , int r){//建树
        tag[u] = 0;
        if(l == r){
            T[u] = A[l];//到叶子节点赋值
            return;
        }
        Build(lc , l , mid) , Build(rc , mid + 1 , r);
        maintain(u);//上传
    }

    inline void Modify(int u , int l , int r , int p , int x){ //单点修改
        if(l == r){
            T[u] = x;//到叶子节点要改
            return;
        } 
        pushdown(u , l , r);// 每次往下递归都要下放懒标记
        if(p <= mid) Modify(lc , l , mid , p , x);// 需要修改的点再mid左边
        else Modify(rc , mid + 1 , r , p , x);//在mid的右边
        maintain(u);    
    }

    inline void Add(int u , int l , int r , int L , int R , int x){ //区间加
        if(l >= L && r <= R) { Tag(u , l , r , x) ; return;}// 需要修改的区间包含了递归的这段区间了，直接修改
        pushdown(u , l , r);
        if(L <= mid) Add(lc , l , mid , L , R , x);// 如果本区间左边需要修改 ， 左边改掉
        if(mid + 1 <= R) Add(rc , mid + 1 , r , L , R , x);// 如果本区间右边需要修改 ， 右边改掉
        maintain(u);
    }

    inline int Ask(int u , int l , int r , int L , int R){ // 区间查询
        if(l >= L && r <= R){// 需要查询的区间包含了递归到的这段区间了 ， 直接反回这段区间的值
            return T[u];
        }
        pushdown(u , l , r);
        if(mid >= R) return Ask(lc , l , mid , L , R);// 如果 需要查的区间在整段区间左边
        if(mid < L) return Ask(rc , mid + 1 , r , L , R);//在右边
        return Ask(lc , l , mid , L , R) + Ask(rc , mid + 1 , r , L , R);//不然两边都递归
    }
#undef lc
#undef rc
#undef mid
}
//using namespace SegmentTree // 写了下面就不用再SegmentTree:: 了

signed main(){
    ios::sync_with_stdio(false) , cin.tie(0);
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++){
        cin >> A[i];
    }

    SegmentTree::Build(1 , 1 , n);

    int k , x , y;
    for (int i = 1 ; i <= m ; i++){     
        cin >> k >> x >> y;
        if(k == 1){
            int c;
            cin >> c;
            SegmentTree::Add(1 , 1 , n , x , y , c);
        }
        if(k == 2){
            cout << SegmentTree::Ask(1 , 1 , n , x , y) << '\n';
        }
    }
    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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;

int n , m , p;
int A[N];

namespace SegmentTree{
#define lc (u << 1)
#define rc (u << 1 | 1)
#define mid ((l + r) >> 1)
    int T[N << 2] , add[N << 2] , mul[N << 2];
    inline void maintain(int u){
        T[u] = (T[lc] + T[rc]) % p;
    }

    inline void pushdown(int u , int l , int r){// 下放到左右区间，本区间标记初始化
        add[lc] = (add[lc] * mul[u]), add[rc] = (add[rc] * mul[u]);// 加的标记 需要乘 乘的标记
        mul[lc] = (mul[lc] * mul[u]) % p , mul[rc] = (mul[rc] * mul[u]) % p;//乘的一样
        add[lc] = (add[lc] + add[u]) % p , add[rc] = (add[rc] + add[u]) % p;//乘完再加
        T[lc] = (T[lc] * mul[u] + (mid - l + 1) * add[u]) % p;//修改区间值
        T[rc] = (T[rc] * mul[u] + (r - mid) * add[u]) % p;
        add[u] = 0; mul[u] = 1;
    }

    inline void Build(int u , int l , int r){
        add[u] = 0;
        mul[u] = 1;// 乘法最小值得为1
        if(l == r){
            T[u] = A[l];
            return;
        }
        Build(lc , l , mid) , Build(rc , mid + 1 , r);
        maintain(u);
    }

    inline void Add(int u , int l , int r , int L , int R , int x){// 区间加
        if(l >= L && r <= R){
            add[u] = (add[u] + x) % p; T[u] = (T[u] + (r - l + 1) * x) % p;
            return;
        }
        pushdown(u , l , r);
        if(L <= mid) Add(lc , l , mid , L , R , x);
        if(mid < R) Add(rc , mid + 1 , r , L , R , x);
        maintain(u); 
    }

    inline void Mul(int u , int l , int r , int L , int R , int x){// 区间乘
        if(l >= L && r <= R){
            mul[u] = (mul[u] * x) % p; add[u] = (add[u] * x) % p ; T[u] = T[u] * x % p;
            return;
        }
        pushdown(u , l , r);
        if(L <= mid) Mul(lc , l , mid , L , R , x);
        if(mid < R) Mul(rc , mid + 1 , r , L , R , x);
        maintain(u);
    }

    inline int Ask(int u , int l , int r , int L , int R){//区间查询
        if(l >= L && r <= R){
            return T[u];
        }
        pushdown(u , l , r);
        if(R <= mid) return Ask(lc , l , mid , L , R);
        if(L > mid) return Ask(rc , mid + 1 , r , L , R);
        return (Ask(lc , l , mid , L , R) + Ask(rc , mid + 1 , r , L , R)) % p;
    }   
#undef lc
#undef rc
#undef mid
}

signed main(){
    ios::sync_with_stdio(false) , cin.tie(0);
    cin >> n >> m >> p;
    for (int i = 1 ; i <= n ; i++){
        cin >> A[i];
    }

    SegmentTree::Build(1 , 1 , n);

    for (int i = 1 ; i <= m ; i++){
        int op , l , r , k;
        cin >> op >> l >> r;
        if(op == 1){
            cin >> k;
            SegmentTree::Mul(1 , 1 , n , l , r , k);
        }
        if(op == 2){
            cin >> k;
            SegmentTree::Add(1 , 1 , n , l , r , k);
        }
        if(op == 3){
            cout << SegmentTree::Ask(1 , 1 , n , l , r) % p << "\n";
        } 
    }

    return 0;
}

题目精选

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
[P2023 AHOI2009\] 维护序列](https://www.luogu.com.cn/problem/P2023)

[P4145 上帝造题的七分钟 2 / 花神游历各国](https://www.luogu.com.cn/problem/P4145)

[P4513 小白逛公园](https://www.luogu.com.cn/problem/P4513)

[P1471 方差](https://www.luogu.com.cn/problem/P1471)

[P6327 区间加区间 sin 和](https://www.luogu.com.cn/problem/P6327)

[P2572 SCOI2010\] 序列操作](https://www.luogu.com.cn/problem/P2572)

信息上传

我们用 \(maintain\) 函数把子节点的信息上传。

1
2
3
4
5
void maintain(int p){
    tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
    tree[p].maxn=max(tree[p<<1].maxn,tree[p<<1|1].maxn);
    tree[p].minx=min(tree[p<<1].minx,tree[p<<1|1].minx);
}

实际使用时需要维护什么信息写什么即可，这里列出一部分给大家参考。

这里的 \(p<<1\) 相当于 \(p*2\) ，\(p<<1|1\) 相当于 \(p*2+1\) 。平时根据个人习惯选择使用即可。

我们可以在前面加两个定义：

1
2
#define lp p<<1
#define rp p<<1|1

于是我们就可以这样写：

1
2
3
4
5
void maintain(int p){
    tree[p].sum=tree[lp].sum+tree[rp].sum;
    tree[p].maxn=max(tree[lp].maxn,tree[rp].maxn);
    tree[p].minx=min(tree[lp].minx,tree[rp].minx);
}

建树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void build(int p,int l,int r){
    tree[p].l=l;
    tree[p].r=r;
    tree[p].tag=0;
    if(l==r){
        tree[p].sum=tree[p].maxn=tree[p].minx=a[l];//这里也是需要用到什么写什么即可
        return;
    }
    int mid=l+r>>1;
    build(lp,l,mid),build(rp,mid+1,r);
    maintain(p);
}

如果你需要维护乘法懒标记，记得将标记初始值赋为 \(1\) ，否则会出问题（因为 \(0\) 乘任何数都是 \(0\) ）。示例见最下方代码实现部分。

懒标记下传

只包含区间加的懒标记下传：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void pushdown(int p){
    if(tree[p].tag){//如果懒标记存在,就执行下面的标记下传工作
        tree[lp].sum+=(tree[lp].r-tree[lp].l+1)*c;
        tree[rp].sum+=(tree[rp].r-tree[rp].l+1)*c;
        tree[lp].maxn+=c;
        tree[rp].maxn+=c;//需要用到就写，这里是为了提供示例
        tree[lp].tag+=c;
        tree[rp].tag+=c;
        tree[p].tag=0;//懒标记下传后记得清空
    }
}

同时包含区间加和区间乘的懒标记下传：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void pushdown(int p){
    tree[lp].sum=(tree[lp].sum*tree[p].mul+(tree[lp].r-tree[lp].l+1)*tree[p].add);
    tree[rp].sum=(tree[rp].sum*tree[p].mul+(tree[rp].r-tree[rp].l+1)*tree[p].add);
    tree[lp].mul*=tree[p].mul;
    tree[rp].mul*=tree[p].mul;
    tree[lp].add+=tree[p].add;
    tree[rp].add+=tree[p].add;
    tree[p].mul=1;
    tree[p].add=0;//记得复原懒标记
    return;
}

这里的 \(mul\) 和 \(add\) 分别为乘和加的懒标记。

以上两种标记下传，一个比较常用，一个代码比较难调，这里代码都已经给出。实际上有很多难度较大的题中的懒标记下传需要自己来设计，那就需要自己多练题总结思路和经验。

修改操作

区间修改

区间加：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void add(int p,int l,int r,int c){//区间内每个数都加上c
    if(tree[p].l>=l&&tree[p].r<=r){//需要修改的区间包含了这个节点维护的区间，下文同理
        tree[p].sum+=(tree[p].r-tree[p].l+1)*c;//区间内共有tree[p].r-tree[p].l+1个数，这些数都要加上c
        tree[p].maxn+=c;//区间最大值加上c
        tree[p].minx+=c;//区间最小值加上c
        tree[p].tag+=c;//懒标记更新
        return;
    }
    pushdown(p);//记得下传懒标记
    int mid=tree[p].l+tree[p].r>>1;
    if(l<=mid)add(lp,l,r,c);
    if(r>mid)add(rp,l,r,c);
    maintain(p);
}

tips：\(tree[p].l+tree[p].r>>1\) 等同于 \((l+r)/2\) ，这里 \(l+r\) 无需带括号的原因是 \(+\) 的优先级高于位运算。

区间乘：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void mul(int p,int l,int r,int c){//区间内每个数都乘上c
    if(tree[p].l>=l&&tree[p].r<=r){
        tree[p].sum*=c;
        tree[p].maxn*=c;
        tree[p].minx*=c;
        tree[p].mul*=c;
        tree[p].add*=c;
        return;
    }
    pushdown(p);
    int mid=tree[p].l+tree[p].r>>1;
    if(l<=mid)mul(lp,l,r,c);
    if(r>mid)mul(rp,l,r,c);
    maintain(p);
}

单点修改

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void update(int p,int x,int c){//将位置x上的数的值修改为c
    if(tree[p].l==tree[p].r){
        tree[p].sum=tree[p].maxn=tree[p].minx=c;
        return;
    }
    pushdown(p);
    int mid=tree[p].l+tree[p].r>>1;
    if(x<=mid)update(lp,x,c);
    else update(rp,x,c);
    maintain(p);
}

实际上可以直接用区间修改来做到单点修改，只需要查询时像这样调用函数 \(add(1,l,l,c)\) （左端点和右端点都为 \(l\) ）即可。

单点查询同理，下文不再赘述。

查询操作

单点查询

1
2
3
4
5
6
7
int ask(int p,int x){
    if(tree[p].l==tree[p].r)return tree[p].sum;//或者tree[p].maxn/tree[p].minx
    pushdown(p);
    int mid=tree[p].l+tree[p].r>>1;
    if(x<=mid)return ask(lp,x);
    else return ask(rp,x);
}

代码实现

下面给出两个结构体线段树代码实现的示例。

仅区间加：

 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
#include<bits/stdc++.h>
#define lp p<<1
#define rp p<<1|1
using namespace std;
const int N=1e5+10;
int n,m,a[N];
struct node{
    int l,r,sum,tag;
}tree[N<<2];
void maintain(int p){
    tree[p].sum=tree[lp].sum+tree[rp].sum;
}
void build(int p,int l,int r){
    tree[p].l=l;
    tree[p].r=r;
    tree[p].tag=0;
    if(l==r){
        tree[p].sum=a[l];
        return;
    }
    int mid=l+r>>1;
    build(lp,l,mid),build(rp,mid+1,r);
    maintain(p);
}
void pushdown(int p){
    if(tree[p].tag){
        tree[lp].sum+=(tree[lp].r-tree[lp].l+1)*tree[p].tag;
        tree[rp].sum+=(tree[rp].r-tree[rp].l+1)*tree[p].tag;
        tree[lp].tag+=tree[p].tag;
        tree[rp].tag+=tree[p].tag;
        tree[p].tag=0;
    }
}
void add(int p,int l,int r,int c){
    if(tree[p].l>=l&&tree[p].r<=r){
        tree[p].sum+=(tree[p].r-tree[p].l+1)*c;
        tree[p].tag+=c;
        return;
    }
    pushdown(p);
    int mid=tree[p].l+tree[p].r>>1;
    if(l<=mid)add(lp,l,r,c);
    if(r>mid)add(rp,l,r,c);
    maintain(p);
}
int ask(int p,int l,int r){
    if(tree[p].l>=l&&tree[p].r<=r)return tree[p].sum;
    pushdown(p);
    int mid=tree[p].l+tree[p].r>>1,ans=0;
    if(l<=mid)ans+=ask(lp,l,r);
    if(r>mid)ans+=ask(rp,l,r);
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);//请一定要记得建树，这一步很容易被忽略，忽略后很不容易被发现
    for(int i=1;i<=m;i++){
        int op;//op为操作类型
        cin>>op;
        if(op==1){
            int x,y,k;
            cin>>x>>y>>k;
            add(1,x,y,k);//区间[x,y]内的每一个数加上k 
        }
        else{
            int x,y;
            cin>>x>>y;
            cout<<ask(1,x,y)<<'\n';//询问区间[x,y]的区间和 
        }
    }
    return 0;
}

例题

P4939 Agent2

P1253 扶苏的问题

P1471 方差

P4145 上帝造题的七分钟 2 / 花神游历各国

P4513 小白逛公园

P6327 区间加区间 sin 和

P2572 [SCOI2010] 序列操作