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

线段树

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

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;
}