Akira的OI(咸鱼)圈

线段树入门

算法
Word count: 1,043 / Reading time: 6 min
2018/07/26 Share

线段树主要应用于区间修改、区间查询，相对于遍历数组查询有着较好的时间复杂度，相对于二维数组预处理有着较好的空间复杂度，相对于RMQ增添了修改功能，有时可以与树状数组互换。线段树的原理以其原数为叶子结点，其区间所需操作为父结点(如求最大值时，其区间最大值即为其父结点的值)。举个例子，以1、2、3、4求最大值建树，[1]、[2]的父结点是[1,2]，其值为2，[1,2]、[3,4]的父结点是[1,4]，其值为4。线段树查询的优越性在于已经预处理了所需区间而空间复杂度比二维数组更优，其修改的优越性在于添加了Lazy Tag，可以将修改延后到查询时，从而降低了时间复杂度，即只修改我们要查询的。修改时，应先修改Mulmark，再修改Addmark，在修改Mulmark时同时将Addmark乘以相应倍数，而先修改Addmark再修改Mulmark则是不行的。值得注意的是,线段树所需空间为4n而非理论所需的2n。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define maxn 100001
using namespace std;
inline ll read()
{
    ll l=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        l=(l<<3)+(l<<1)+(ch^'0');
        ch=getchar();
    }
    return w*l;
}
struct pp
{
    ll data,addmark,mulmark=1;
}tree[maxn<<2];
ll arr[maxn],n,p;
inline void Pushup(int rt)
{
    tree[rt].data=tree[rt<<1].data%p+tree[rt<<1|1].data%p;
    tree[rt].data%=p;
}
inline void Pushdown(int rt,int l,int r)
{
    if(tree[rt].mulmark!=1)
    {
        tree[rt<<1].mulmark*=tree[rt].mulmark;
        tree[rt<<1|1].mulmark*=tree[rt].mulmark;
        tree[rt<<1].addmark*=tree[rt].mulmark;
        tree[rt<<1|1].addmark*=tree[rt].mulmark;
        tree[rt<<1].data*=tree[rt].mulmark;
        tree[rt<<1|1].data*=tree[rt].mulmark;
        tree[rt<<1].mulmark%=p;
        tree[rt<<1|1].mulmark%=p;
        tree[rt<<1].addmark%=p;
        tree[rt<<1|1].addmark%=p;
        tree[rt<<1].data%=p;
        tree[rt<<1|1].data%=p;
        tree[rt].mulmark=1;
    }
    if(tree[rt].addmark)
    {
        tree[rt<<1].addmark+=tree[rt].addmark;
        tree[rt<<1|1].addmark+=tree[rt].addmark;
        tree[rt<<1].data+=l*tree[rt].addmark;
        tree[rt<<1|1].data+=r*tree[rt].addmark;
        tree[rt<<1].addmark%=p;
        tree[rt<<1|1].addmark%=p;
        tree[rt<<1].data%=p;
        tree[rt<<1|1].data%=p;
        tree[rt].addmark=0;
    }
}
void Build(int l,int r,int rt)
{
    if(l==r)
    {
        tree[rt].data=arr[l];
        return;
    }
    int m=(l+r)>>1;
    Build(l,m,rt<<1);
    Build(m+1,r,rt<<1|1);
    Pushup(rt);
}
void Add(int nl,int nr,ll k,int l,int r,int rt)
{
    if(nl<=l&&nr>=r)
    {
        tree[rt].data+=(r-l+1)*k;
        tree[rt].addmark+=k;
        tree[rt].data%=p;
        tree[rt].addmark%=p;
        return;
    }
    int m=(l+r)>>1;
    Pushdown(rt,m-l+1,r-m);
    if(nl<=m)
        Add(nl,nr,k,l,m,rt<<1);
    if(nr>m)
        Add(nl,nr,k,m+1,r,rt<<1|1);
    Pushup(rt);
}
void Mul(int nl,int nr,ll k,int l,int r,int rt)
{
    if(nl<=l&&nr>=r)
    {
        tree[rt].data*=k;
        tree[rt].addmark*=k;
        tree[rt].mulmark*=k;
        tree[rt].data%=p;
        tree[rt].addmark%=p;
        tree[rt].mulmark%=p;    
        return;
    }
    int m=(l+r)>>1;
    Pushdown(rt,m-l+1,r-m);
    if(nl<=m)
        Mul(nl,nr,k,l,m,rt<<1);
    if(nr>m)
        Mul(nl,nr,k,m+1,r,rt<<1|1);
    Pushup(rt);
}
ll Query(int nl,int nr,int l,int r,int rt)
{
    if(nl<=l&&nr>=r)
        return tree[rt].data%p;
    ll ans=0;
    int m=(l+r)>>1;
    Pushdown(rt,m-l+1,r-m);
    if(nl<=m)
        ans+=Query(nl,nr,l,m,rt<<1),ans%=p;
    if(nr>m)
        ans+=Query(nl,nr,m+1,r,rt<<1|1),ans%=p;
    return ans%p;
}
int main()
{
    ll m,z,x,y,k;
    n=read(),m=read(),p=read();
    for(int i=1;i<=n;i++)
        arr[i]=read();
    Build(1,n,1);
    while(m--)
    {
        z=read(),x=read(),y=read();
        if(z==1)
            k=read(),Mul(x,y,k,1,n,1);
        if(z==2)
            k=read(),Add(x,y,k,1,n,1);
        if(z==3)
            printf("%lld\n",Query(x,y,1,n,1));
    }
    return 0;
}

原文作者: Akira

原文链接: https://akira-1231.github.io/2018/07/26/线段树入门/

发表日期: 七月 26日 2018, 9:41:15 晚上

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 11
2018
题解 算法 杂记