线段树

线段树

单点修改，区间查询

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 50010;
 5 typedef long long ll;
 6 int cnt[maxn<<2];
 7 
 8 void Pushup(int pt){
 9     cnt[pt]=cnt[pt<<1]+cnt[pt<<1|1];
10 }
11 
12 //建树Build(1,n,1)
13 void Build(int l,int r, int pt){
14     if(l==r){
15         scanf("%d",&cnt[pt]);
16         return ;
17     }
18     int mid=(l+r)>>1;
19     Build(l,mid,pt<<1);
20     Build(mid+1,r,pt<<1|1);
21     cnt[pt] = cnt[pt<<1]+cnt[pt<<1|1];
22 }
23 
24 //区间查询Query(L,R,1,n,1)
25 int Query(int L,int R,int l,int r,int pt){
26     if( L<=l && R>=r ) return cnt[pt];
27     int sum=0;
28     int mid=(l+r)>>1;
29     if( L<=mid ) sum += Query(L,R,l,mid,pt<<1);
30     if( R>mid ) sum += Query(L,R,mid+1,r,pt<<1|1);
31     return sum;
32 }
33 
34 //单点更新Updata(pos,val,1,n,1)
35 void Updata(int i,int add,int l,int r,int pt){
36     if( l==r ){
37         cnt[pt]+=add;
38         return ;
39     }
40     int mid=(l+r)>>1;
41     if( i<=mid ) Updata(i,add,l,mid,pt<<1);
42     else Updata(i,add,mid+1,r,pt<<1|1);
43     cnt[pt] = cnt[pt<<1]+cnt[pt<<1|1];
44     return ;
45 
46 }
47 
48 
49 int main()
50 {
51     int t,n,c,l,r,i;
52     char cmd[10];
53     scanf("%d",&t);
54     for(c=1;c<=t;c++)
55     {
56         memset(cnt,0,sizeof(cnt));
57         scanf("%d",&n);
58         Build(1,n,1);
59         printf("Case %d:
",c);
60         while( 1 )
61         {
62             scanf("%s",cmd);
63             if( cmd[0]=='E' ) break;            //结束
64             if( cmd[0]=='Q' ){                  //区间询问
65                 scanf("%d%d",&l,&r);
66                 printf("%d
",Query(l,r,1,n,1));
67             }
68             else if( cmd[0]=='A' ){             //单点更新
69                 scanf("%d%d",&i,&l);            //单点加
70                 Updata(i,l,1,n,1);
71             }
72             else{                               //单点减
73                 scanf("%d%d",&i,&l);
74                 Updata(i,-l,1,n,1);
75             }
76         }
77     }
78     return 0;
79 }

区间修改，区间查询

  1 /* */
  2 # include <iostream>
  3 # include <stdio.h>
  4 # include <string.h>
  5 # include <cstdlib>
  6 # include <cmath>
  7 # include <climits>
  8 # include <list>
  9 # include <set>
 10 # include <map>
 11 # include <bitset>
 12 # include <deque>
 13 # include <cctype>
 14 # include <queue>
 15 # include <stack>
 16 # include <vector>
 17 using namespace std;
 18 
 19 typedef long long ll;
 20 const int maxn=1e5+10;
 21 ll sum[maxn<<2], lazy[maxn<<2];
 22 int N, Q;
 23 
 24 void pushup(int pt){
 25     sum[pt] = sum[pt<<1]+sum[pt<<1|1];
 26 }
 27 
 28 void pushdown(int pt, int l, int r)
 29 {
 30     if( lazy[pt] ){
 31         lazy[pt<<1] += lazy[pt];
 32         lazy[pt<<1|1] += lazy[pt];
 33         int m = (r+l)>>1;
 34         sum[pt<<1] += lazy[pt]*(m-l+1);
 35         sum[pt<<1|1] += lazy[pt]*(r-m);
 36         lazy[pt] = 0;
 37     }
 38 }
 39 
 40 void updata(int pt, int l, int r, int L, int R, int addv){
 41     if( L<=l && R>=r )
 42     {
 43         lazy[pt] += addv;
 44         sum[pt] += addv*(r-l+1);
 45         return ;
 46     }
 47 
 48     pushdown(pt, l, r);
 49     int m=(r+l)>>1;
 50     if( L<=m )
 51         updata(pt<<1, l, m, L, R, addv);
 52     if( R>m )
 53         updata(pt<<1|1, m+1, r, L, R, addv);
 54     pushup(pt);
 55 }
 56 
 57 
 58 
 59 void build(int pt, int l, int r)
 60 {
 61     if( l==r ){
 62         scanf("%I64d", &sum[pt]);
 63         return ;
 64     }
 65     int mid = (l+r)>>1;
 66     build(pt<<1, l, mid);
 67     build(pt<<1|1, mid+1, r);
 68     pushup(pt);
 69 }
 70 
 71 ll query(int pt, int l, int r, int L, int R ){
 72     if( L<=l && R>=r )
 73         return sum[pt];
 74     pushdown(pt, l, r);
 75     int m = (r+l)>>1;
 76     ll ans=0;
 77     if( L<=m )
 78         ans += query(pt<<1, l, m, L, R);
 79     if( R>m )
 80         ans += query(pt<<1|1, m+1, r, L, R);
 81     return ans;
 82 }
 83 
 84 int main()
 85 {
 86     int x, y, z;
 87     while( ~ scanf("%d %d", &N, &Q) ){
 88         memset(sum, 0, sizeof(sum));
 89         memset(lazy, 0, sizeof(lazy));
 90         build(1, 1, N);
 91         char str[2];
 92         while( Q-- ){
 93             scanf("%s", str);
 94             if( str[0]=='C' ){
 95                 scanf("%d %d %d", &x, &y, &z);
 96                 updata(1, 1, N, x, y, z);
 97             }
 98             else{
 99                 scanf("%d %d", &x, &y);
100                 printf("%I64d
", query(1, 1, N, x, y));
101             }
102         }
103     }
104     return 0;
105 }