【模板】线段树

线段树区修区查，洛谷3372

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define ls (cur<<1)
 4 #define rs (cur<<1|1)
 5 #define mid ((a[cur].l+a[cur].r)>>1)
 6 #define len(x) (a[x].r-a[x].l+1)
 7 #define LL long long
 8 using namespace std;
 9 const int maxn=800010;
10 LL n,m,k,x,y,z;
11 struct tree{
12     int l,r;
13     LL del,sum; 
14 }a[maxn];
15 void read(LL &k){
16     k=0; int f=1; char c=getchar();
17     while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
18     while ('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();
19     k*=f;
20 }
21 void build(int cur,int l,int r){
22     a[cur].l=l; a[cur].r=r;
23     if (l<r){
24         build(ls,l,mid);
25         build(rs,mid+1,r);
26         a[cur].sum=a[ls].sum+a[rs].sum;
27     }
28     else read(a[cur].sum);
29 }
30 void pushdown(int cur){
31     if (a[cur].l==a[cur].r||a[cur].del==0) return;
32     a[ls].del+=a[cur].del; a[ls].sum+=len(ls)*a[cur].del;
33     a[rs].del+=a[cur].del; a[rs].sum+=len(rs)*a[cur].del;
34     a[cur].del=0;
35 }
36 void add(int cur,int l,int r,int delta){
37     if (l<=a[cur].l&&a[cur].r<=r){
38         a[cur].del+=delta;
39         a[cur].sum+=len(cur)*delta;
40     }
41     else{
42         pushdown(cur);
43         if (l<=mid) add(ls,l,r,delta);
44         if (r>mid) add(rs,l,r,delta);
45         a[cur].sum=a[ls].sum+a[rs].sum;
46     }
47 }
48 LL query(int cur,int l,int r){
49     if (l<=a[cur].l&&a[cur].r<=r) return a[cur].sum;
50     else{
51         pushdown(cur);
52         LL ret=0;
53         if (l<=mid) ret+=query(ls,l,r);
54         if (r>mid) ret+=query(rs,l,r);
55         return ret;
56     }
57 }
58 int main(){
59     read(n); read(m);
60     build(1,1,n);
61     for (int i=1;i<=m;i++){
62         read(k);
63         if (k==1){
64             read(x); read(y); read(z);
65             add(1,x,y,z);
66         }
67         else{
68             read(x); read(y);
69             printf("%lld
",query(1,x,y));
70         }
71     }
72     return 0;
73 }

View Code

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define LL long long
 4 #define ls (cur<<1)
 5 #define rs (cur<<1|1)
 6 #define mid ((a[cur].l+a[cur].r)>>1)
 7 #define len(x) (a[x].r-a[x].l+1)
 8 using namespace std;
 9 const int maxn=800010;
10 LL n,m,x,y,z,k;
11 struct tree{LL l,r,sum,del;}a[maxn];
12 inline void read(LL &k){
13     k=0; int f=1; char c=getchar();
14     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
15     while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();
16     k*=f;
17 }
18 inline void pushup(int cur){a[cur].sum=a[ls].sum+a[rs].sum;}
19 inline void pushdown(int cur){
20     if(!a[cur].del) return; LL D=a[cur].del;
21     a[ls].del+=D; a[ls].sum+=D*len(ls);
22     a[rs].del+=D; a[rs].sum+=D*len(rs);
23     a[cur].del=0;
24 }
25 void build(int cur,int l,int r){
26     a[cur].l=l; a[cur].r=r;
27     if(l<r){
28         build(ls,l,mid); build(rs,mid+1,r); pushup(cur);
29     }
30     else read(a[cur].sum);
31 }
32 void update(int cur,int l,int r,LL del){
33     if(l<=a[cur].l&&a[cur].r<=r){
34         a[cur].del+=del; a[cur].sum+=len(cur)*del; return;
35     }
36     pushdown(cur);
37     if(l<=mid) update(ls,l,r,del); 
38     if(r>mid) update(rs,l,r,del);
39     pushup(cur); 
40 }
41 LL query(int cur,int l,int r){
42     if(l<=a[cur].l&&a[cur].r<=r) return a[cur].sum;
43     pushdown(cur); LL ret=0;
44     if(l<=mid) ret+=query(ls,l,r);
45     if(r>mid) ret+=query(rs,l,r);
46     return ret;
47 }
48 int main(){
49     read(n); read(m); build(1,1,n);
50     for (int i=1;i<=m;i++){
51         read(k); read(x); read(y);
52         if(k==1) read(z),update(1,x,y,z);
53         else printf("%lld
",query(1,x,y));
54     }
55     return 0;
56 }

View Code