POJ-3468 A Simple Problem with Integers

第一次手写的线段树，以后就用这个做模板好了。

自己风格的线段树：（区段更新

 1 #define maxn 100005
 2 #define ls(p) p<<1        //p左子结点下标
 3 #define rs(p) p<<1|1    //p右子结点下标
 4 struct segTree{
 5     int l,r;            //线段左右端点值
 6     int v;                //区间和
 7     int f;                //lazy标记
 8 }t[maxn<<2];
 9 void pushUp(int p){
10     t[p].v=t[ls(p)].v+t[rs(p)].v;
11 }
12 void pushDown(int p){
13     if(t[p].f){
14         t[ls(p)].f+=t[p].f;
15         t[ls(p)].v+=t[p].f*(t[ls(p)].r-t[ls(p)].l+1);
16         t[rs(p)].f+=t[p].f;
17         t[rs(p)].v+=t[p].f*(t[rs(p)].r-t[rs(p)].l+1);
18         t[p].f=0;
19     }
20 }
21 void Build(int p,int l,int r){
22     t[p].l=l;
23     t[p].r=r;
24     t[p].f=0;
25     if(l==r){
26         //init : scanf("%d",&t[p].v);
27         return ;
28     }
29     int m=(l+r)/2;
30     Build(ls(p),l,m);
31     Build(rs(p),m+1,r);
32     pushUp(p);
33 }
34 void upDate(int p,int L,int R,int v){
35     int l=t[p].l,r=t[p].r;
36     if(l>=L && R>=r){
37         t[p].f+=v;
38         t[p].v+=(r-l+1)*v;
39         return ;
40     }
41     pushDown(p);
42     int m=(l+r)/2;
43     if(L<=m) upDate(ls(p),L,R,v);
44     if(R>m) upDate(rs(p),L,R,v);
45     pushUp(p);
46 }
47 int Query(int p,int L,int R){
48     int l=t[p].l,r=t[p].r;
49     if(l>=L && R>=r)
50         return t[p].v;
51     pushDown(p);
52     int ans=0;
53     int m=(l+r)/2;
54     if(L<=m) ans+=Query(ls(p),L,R);
55     if(R>m) ans+=Query(rs(p),L,R);
56     return ans;
57 }

View Code

单点更新：

 1 #define maxn 100005
 2 #define ls(p) p<<1
 3 #define rs(p) p<<1|1
 4 struct segTree{
 5     int l,r;
 6     int v;
 7 }t[maxn<<2];
 8 void pushUp(int p){
 9     t[p].v=t[ls(p)].v+t[rs(p)].v;
10 }
11 void Build(int l,int r,int p){
12     t[p].l=l;
13     t[p].r=r;
14     if(l==r){
15         scanf("%d",&t[p].v);
16         return;
17     }
18     int m=(l+r)/2;
19     Build(l,m,ls(p));
20     Build(m+1,r,rs(p));
21     pushUp(p);
22 }
23 void upDate(int p,int d,int v){
24     int l=t[p].l,r=t[p].r;
25     if(l==r){
26         t[p].v+=v;
27         return;
28     }
29     int m=(l+r)/2;
30     if(d<=m) upDate(ls(p),d,v);
31     else upDate(rs(p),d,v);
32     pushUp(p);
33 }
34 int Query(int p,int L,int R){
35     int l=t[p].l,r=t[p].r;
36     if(L<=l && r<=R)
37         return t[p].v;
38     int m=(l+r)/2;
39     int ans=0;
40     if(L<=m) ans+=Query(ls(p),L,R);
41     if(R>m) ans+=Query(rs(p),L,R);
42     return ans;
43 }

View Code

ac代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 #define maxn 100005
 5 #define ls(p) p<<1
 6 #define rs(p) p<<1|1
 7 struct segTree{
 8     int l,r;
 9     long long v;
10     long long f;
11 }t[maxn<<2];
12 void pushUp(int p){
13     t[p].v=t[ls(p)].v+t[rs(p)].v;
14 }
15 void pushDown(int p){
16     if(t[p].f){
17         t[ls(p)].f+=t[p].f;
18         t[ls(p)].v+=t[p].f*(t[ls(p)].r-t[ls(p)].l+1);
19         t[rs(p)].f+=t[p].f;
20         t[rs(p)].v+=t[p].f*(t[rs(p)].r-t[rs(p)].l+1);
21         t[p].f=0;
22     }
23 }
24 void Build(int p,int l,int r){
25     t[p].l=l;
26     t[p].r=r;
27     t[p].f=0;
28     if(l==r){
29         //init
30         scanf("%lld",&t[p].v);
31         return ;
32     }
33     int m=(l+r)/2;
34     Build(ls(p),l,m);
35     Build(rs(p),m+1,r);
36     pushUp(p);
37 }
38 void upDate(int p,int L,int R,int v){
39     int l=t[p].l,r=t[p].r;
40     if(l>=L && R>=r){
41         t[p].f+=v;
42         t[p].v+=(r-l+1)*v;
43         return ;
44     }
45     pushDown(p);
46     int m=(l+r)/2;
47     if(L<=m) upDate(ls(p),L,R,v);
48     if(R>m) upDate(rs(p),L,R,v);
49     pushUp(p);
50 }
51 long long Query(int p,int L,int R){
52     int l=t[p].l,r=t[p].r;
53     if(l>=L && R>=r)
54         return t[p].v;
55     pushDown(p);
56     long long ans=0;
57     int m=(l+r)/2;
58     if(L<=m) ans+=Query(ls(p),L,R);
59     if(R>m) ans+=Query(rs(p),L,R);
60     return ans;
61 }
62 int main(){
63     int N,Q;
64     while(~scanf("%d%d",&N,&Q)){
65         Build(1,1,N);
66         while(Q--){
67             char op[2];
68             scanf("%s",op);
69             if(op[0]=='Q'){
70                 int a,b;
71                 scanf("%d%d",&a,&b);
72                 printf("%lld
",Query(1,a,b));
73             }else{
74                 int a,b,v;
75                 scanf("%d%d%d",&a,&b,&v);
76                 upDate(1,a,b,v);
77             }
78         }
79     }
80     return 0;
81 }

View Code

最近发现树状数组也能做区间更新+区间询问，也是炫酷。。。有必要收藏一下：

详见：http://blog.csdn.net/q573290534/article/details/6664454

 1 #include<map>
 2 #include<set>
 3 #include<list>
 4 #include<cmath>
 5 #include<ctime>
 6 #include<queue>
 7 #include<stack>
 8 #include<cctype>
 9 #include<cstdio>
10 #include<string>
11 #include<vector>
12 #include<cstdlib>
13 #include<cstring>
14 #include<complex>
15 #include<utility>    //pair
16 #include<iostream>
17 #include<algorithm>
18 #define MAXN 100005
19 #define INF 0x3f3f3f3f
20 #define LL long long
21 #define DBL double
22 #define EPS 1e-6
23 #define PI acos(-1.0)
24 #define Test() cout<<"Test"<<endl;
25 #define Debug(a) cout<<#a<<" = "<<a<<endl;
26 #define Debug2(a,b) cout<<#a<<" = "<<a<<" , "<<#b<<" = "<<b<<endl;
27 using namespace std;
28 
29 LL a[MAXN], b[MAXN], c[MAXN], n, m;
30 
31 void addB(int p, LL v){
32     for(int i=p; i; i-=i&(-i))
33         b[i]+=v;
34 }
35 LL sumB(int p){
36     LL s=0;
37     for(int i=p; i<=n; i+=i&(-i))
38         s+=b[i];
39     return s;
40 }
41 void addC(int p, LL v){
42     for(int i=p; i<=n; i+=i&(-i))
43         c[i]+=p*v;        //p*v
44 }
45 LL sumC(int p){
46     LL s=0;
47     for(int i=p; i; i-=i&(-i))
48         s+=c[i];
49     return s;
50 }
51 LL query(int x){
52     return x? sumB(x)*x+sumC(x-1): 0;
53 }
54 
55 // poj 3468
56 int main(){
57     while(cin >>n >>m){
58         a[0]=0;
59         for(int i=1, t; i<=n; i++){    
60             scanf("%d", &t);
61             a[i] = a[i-1]+t;
62         }
63         memset(b, 0, sizeof(b));
64         memset(c, 0, sizeof(c));
65         while(m--){
66             char cmd[5];
67             int l, r, v;
68             scanf("%s", cmd);
69             if(cmd[0] == 'Q'){
70                 scanf("%d%d", &l, &r);
71                 printf("%lld
", query(r)-query(l-1)+a[r]-a[l-1]);
72             }else{
73                 scanf("%d%d%d", &l, &r, &v);
74                 addB(r, v); addC(r, v);
75                 if(l>1)
76                 { addB(l-1, -v); addC(l-1, -v); }
77             }
78             
79         }
80     }
81     return 0;
82 }

View Code