最近复习一下线段树的板子。

线段树

就随便写吧,就写给自己看看的,因为即便是我学过板子,也基本会交错很多次。首先一个就是一定在开头加上一句话:

1
#define int long long

然后就是push_down的操作,一定是有标记的时候已经加完了,push_down的时候就是把标记分发下去然后给子节点加上值和lazy标记。

在add操作的时候一定要加上先push_down再加。

线段树解决问题的范围

要求在线,并且含有区间加法和区间查询的操作,下面是洛谷的板子题并给出标程,也可以当板子用。

板子

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
#define maxn 1000005
using namespace std;
struct eee{
int lazy;
int l;
int r;
int sum;
int operator+(const eee &a){
return sum+a.sum;
}
int length(){
return (r-l+1);
}
int mid(){
return l+r>>1;
}
}tree[maxn<<1];
int a[maxn],ans;
inline void build(int l,int r ,int now){
tree[now].l=l;
tree[now].r=r;
if(l==r){
tree[now].sum=a[l];
return;
}
int mid=l+r>>1;
build(l,mid,now<<1);
build(mid+1,r,now<<1|1);
tree[now].sum=tree[now<<1]+tree[now<<1|1];
}
inline void push_down(int now){
//if(tree[now].l==tree[now].r)return;
int lazy=tree[now].lazy;
tree[now<<1].sum+=lazy*tree[now<<1].length();
tree[now<<1].lazy+=lazy;
tree[now<<1|1].sum+=lazy*tree[now<<1|1].length();
tree[now<<1|1].lazy+=lazy;
tree[now].lazy=0;

}
inline void add(int l,int r,int num,int i){
if(l<=tree[i].l&&r>=tree[i].r){
tree[i].sum+=num*(tree[i].r-tree[i].l+1);
//tree[i].sum%=mod;
tree[i].lazy+=num;
}
else{
int mid=tree[i].l+tree[i].r>>1;
if(tree[i].lazy)push_down(i);
if(l<=mid)add(l,r,num,i<<1);
if(r>mid)add(l,r,num,i<<1|1);
tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum);//%mod;
}
}

inline void query(int l,int r,int i){
if(l<=tree[i].l&&r>=tree[i].r){
ans+=tree[i].sum;
// ans%=mod;
}
else{
if(tree[i].lazy)push_down(i);
int mid=tree[i].l+tree[i].r>>1;
if(l<=mid)query(l,r,i<<1);
if(r>mid)query(l,r,i<<1|1);
}
}
void sync(){
//freopen("1.in","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}

signed main(){
sync();
int n,t;
cin>>n>>t;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,n,1);
while(t--){
int op,x,y,z;
cin>>op;
if(op==1){
cin>>x>>y>>z;
add(x,y,z,1);
}
else{
cin>>x>>y;
ans=0;
query(x,y,1);
cout<<ans<<endl;
}
}
return 0;
}