「模板」线段树

【模板】线段树 1

线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)

Code

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>
using namespace std;

#define ll long long
#define RE register
#define maxn 100010

ll f[maxn<<2],a[maxn],tag[maxn<<2];
ll n,m,t,x,y,v;

inline ll ls(ll x){return x<<1;}

inline ll rs(ll x){return x<<1|1;}

inline void fread(ll &x){
x=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
}

inline void add(ll k,ll l,ll r,ll v){
tag[k]+=v;
f[k]+=v*(r-l+1);
}

inline void push_tag(ll k,ll l,ll r){
ll v=tag[k];
if(v==0)return;
ll mid=(l+r)>>1;
add(ls(k),l,mid,v);
add(rs(k),mid+1,r,v);
tag[k]=0;
}

inline void build(ll k,ll l,ll r){
tag[k]=0;
if(l==r){
f[k]=a[l];
return;
}
ll mid=(l+r)>>1;
build(ls(k),l,mid);
build(rs(k),mid+1,r);
f[k]=f[ls(k)]+f[rs(k)];
}

inline void update(ll k,ll l,ll r,ll x,ll y,ll v){
if(x<=l&&y>=r){
tag[k]+=v;
f[k]+=v*(r-l+1);
return;
}
ll mid=(l+r)>>1;
push_tag(k,l,r);
if(x<=mid)update(ls(k),l,mid,x,y,v);
if(y>mid)update(rs(k),mid+1,r,x,y,v);
f[k]=f[ls(k)]+f[rs(k)];
}

inline ll ask(ll k,ll l,ll r,ll x,ll y){
if(x<=l&&y>=r){
return f[k];
}
ll mid=(l+r)>>1;
push_tag(k,l,r);
ll ans=0;
if(x<=mid)ans+=ask(ls(k),l,mid,x,y);
if(y>mid)ans+=ask(rs(k),mid+1,r,x,y);
return ans;
}

int main(){
fread(n);
fread(m);
for(RE int i=1;i<=n;i++)fread(a[i]);
build(1,1,n);
for(RE int i=1;i<=m;i++){
fread(t);
if(t==1){
fread(x);
fread(y);
fread(v);
update(1,1,n,x,y,v);
}
if(t==2){
fread(x);
fread(y);
printf("%lld\n",ask(1,1,n,x,y));
}
}
return 0;
}

【模板】线段树 2

Code

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

#define RE register
#define ll long long
#define maxn 100010

ll f[maxn<<2],a[maxn],add[maxn<<2],mul[maxn<<2];
ll n,m,x,y,v,t,p;

inline ll ls(ll x){return x<<1;}

inline ll rs(ll x){return x<<1|1;};

inline void fread(ll &x){
x=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x*=f;
}

inline void push_tag(ll k,ll l,ll r){
ll m=mul[k],a=add[k];
ll mid=(l+r)>>1;
mul[ls(k)]=mul[ls(k)]*m%p;
mul[rs(k)]=mul[rs(k)]*m%p;

add[ls(k)]=(add[ls(k)]*m%p+a)%p;
add[rs(k)]=(add[rs(k)]*m%p+a)%p;

f[ls(k)]=f[ls(k)]*m%p+a*(mid-l+1)%p;
f[rs(k)]=f[rs(k)]*m%p+a*(r-mid)%p;

mul[k]=1;
add[k]=0;
}

inline void build(ll k,ll l,ll r){
add[k]=0;
mul[k]=1;
if(l==r){
f[k]=a[l]%p;
return;
}
ll mid=(l+r)>>1;
build(ls(k),l,mid);
build(rs(k),mid+1,r);
f[k]=f[ls(k)]+f[rs(k)];
}

inline void up_add(ll k,ll l,ll r,ll x,ll y,ll v){
if(x<=l&&y>=r){
add[k]=(add[k]+v)%p;
f[k]=(f[k]+v*(r-l+1)%p)%p;
return;
}
ll mid=(l+r)>>1;
push_tag(k,l,r);
if(x<=mid)up_add(ls(k),l,mid,x,y,v);
if(y>mid)up_add(rs(k),mid+1,r,x,y,v);
f[k]=(f[ls(k)]+f[rs(k)])%p;
}

inline void up_mul(ll k,ll l,ll r,ll x,ll y,ll v){
if(x<=l&&y>=r){
mul[k]=mul[k]*v%p;
add[k]=add[k]*v%p;
f[k]=f[k]*v%p;
return;
}
ll mid=(l+r)>>1;
push_tag(k,l,r);
if(x<=mid)up_mul(ls(k),l,mid,x,y,v);
if(y>mid)up_mul(rs(k),mid+1,r,x,y,v);
f[k]=(f[ls(k)]+f[rs(k)])%p;
}

inline ll ask(ll k,ll l,ll r,ll x,ll y){
if(x<=l&&y>=r){
return f[k]%p;
}
ll mid=(l+r)>>1;
push_tag(k,l,r);
ll ans=0;
if(x<=mid)ans+=ask(ls(k),l,mid,x,y)%p;
if(y>mid)ans+=ask(rs(k),mid+1,r,x,y)%p;
return ans;
}

int main(){
fread(n);
fread(m);
fread(p);
for(RE int i=1;i<=n;i++)fread(a[i]);
build(1,1,n);
for(RE int i=1;i<=m;i++){
fread(t);
if(t==1){
fread(x);
fread(y);
fread(v);
up_mul(1,1,n,x,y,v);
}
if(t==2){
fread(x);
fread(y);
fread(v);
up_add(1,1,n,x,y,v);
}
if(t==3){
fread(x);
fread(y);
printf("%lld\n",ask(1,1,n,x,y)%p);
}
}
return 0;
}
0%