数列操作问题

线段树或树状数组

 1 线段树
 2 #include <stdio.h>
 3 int sum[100001];
 4 struct node
 5 {
 6     int v, a, b, left, right;
 7 };
 8 node tree[200100];
 9 int tot=0, d, k, s, t;
10 void maketree(int a, int b)
11 {
12     int now;
13     tot++;
14     now=tot;
15     tree[now].a=a;
16     tree[now].b=b;
17     tree[now].v=sum[b]-sum[a-1];
18     if(a<b)
19     {
20         tree[now].left=tot+1;
21         maketree(a, (a+b)/2);
22         tree[now].right=tot+1;
23         maketree((a+b)/2+1, b);
24     }
25 }
26 void change(int r)
27 {
28     tree[r].v+=d;
29     if(tree[r].left!=0&&tree[tree[r].left].a<=k&&tree[tree[r].left].b>=k)
30     change(tree[r].left);
31     if(tree[r].right!=0&&tree[tree[r].right].a<=k&&tree[tree[r].right].b>=k)
32     change(tree[r].right);
33 }
34 int getsum(int r)
35 {
36     int la, lb, ra, rb;
37     int tot=0;
38     if(s<=tree[r].a&&tree[r].b<=t)    return tree[r].v;
39     else
40     {
41         la=tree[tree[r].left].a;
42         lb=tree[tree[r].left].b;
43         if(!(la>t||lb<s))    tot=tot+getsum(tree[r].left);
44         ra=tree[tree[r].right].a;
45         rb=tree[tree[r].right].b;
46         if(!(ra>t||rb<s))    tot=tot+getsum(tree[r].right);
47         return tot;
48     }
49 }
50 int main()
51 {
52     int n, i, m;
53     char temp;
54     scanf("%d", &n);
55     scanf("%d", &sum[1]);
56     for(i=2; i<=n; i++)
57     {
58         scanf("%d", &sum[i]);
59         sum[i]+=sum[i-1];
60     }
61     maketree(1, n);
62     scanf("%d", &m);
63     for(i=1; i<=m; i++)
64     {
65         getchar();
66         temp=getchar();
67         getchar();
68         getchar();
69         if(temp=='S')
70         {
71             scanf("%d%d", &s, &t);
72             printf("%d
", getsum(1));
73         }
74         if(temp=='A')
75         {
76             scanf("%d%d", &k, &d);
77             change(1);
78         }
79     }
80     return 0;
81 }

线段树

 1 /*
 2 lrj's code
 3 used to test it could ac
 4 
 5 */
 6 #include<cstdio>
 7 using namespace std;
 8 #define maxn 100005
 9 int c[maxn];
10 int n,m,data,l,r,k;
11 char t;
12 inline int lowbit(int i){return i&(-i);}
13 int main()
14 {
15     scanf("%d",&n);
16     for(int i=1;i<=n;++i)
17     {
18         scanf("%d",&data);
19         for(int j=i;j<=n;j+=lowbit(j)) c[j]+=data;
20     }
21     for(scanf("%d",&m);m;--m)
22     {
23         t=getchar();
24         while(t<'A'||t>'Z') t=getchar();
25         if(t=='A') 
26         {
27             while(t>='A'&&t<='Z') t=getchar();
28             scanf("%d%d",&k,&data);
29             for(int j=k;j<=n;j+=lowbit(j)) c[j]+=data;
30         }
31         else
32         {
33             while(t>='A'&&t<='Z') t=getchar();
34             data=0;scanf("%d%d",&l,&r);
35             for(int j=r;j;j-=lowbit(j)) data+=c[j];
36             for(int j=l-1;j;j-=lowbit(j)) 
37             data-=c[j];
38             printf("%d
",data);            
39         }
40     }
41     return 0;
42 }

树状数组