士兵杀敌（二）（线段树+树状数组）

士兵杀敌（二）

时间限制：1000 ms | 内存限制：65535 KB

难度：5

描述

南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。

小工是南将军手下的军师，南将军经常想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。

南将军的某次询问之后士兵i可能又杀敌q人，之后南将军再询问的时候，需要考虑到新增的杀敌数。

输入

只有一组测试数据第一行是两个整数N,M，其中N表示士兵的个数(1<N<1000000)，M表示指令的条数。(1<M<100000) 随后的一行是N个整数，ai表示第i号士兵杀敌数目。(0<=ai<=100) 随后的M行每行是一条指令，这条指令包含了一个字符串和两个整数，首先是一个字符串，如果是字符串QUERY则表示南将军进行了查询操作，后面的两个整数m,n，表示查询的起始与终止士兵编号；如果是字符串ADD则后面跟的两个整数I,A(1<=I<=N,1<=A<=100),表示第I个士兵新增杀敌数为A.

输出

对于每次查询，输出一个整数R表示第m号士兵到第n号士兵的总杀敌数，每组输出占一行

样例输入

5 6
1 2 3 4 5
QUERY 1 3
ADD 1 2
QUERY 1 3
ADD 2 3
QUERY 1 2
QUERY 1 5

样例输出

6
8
8
20
线段树：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAX(x,y)(x>y?x:y)
 7 #define MIN(x,y)(x<y?x:y)
 8 #define lson root<<1,l,mid
 9 #define rson root<<1|1,mid+1,r
10 #define NOW tree[root].val=tree[root<<1].val+tree[root<<1|1].val;
11 #define L tree[root].l
12 #define R tree[root].r
13 #define V tree[root].val
14 //#define LOCAL
15 const int INF=0x3f3f3f3f;
16 const int MAXN=1000010;
17 struct Node{
18     int l,r,val;
19 }; 
20 int X,Y,ans;
21 Node tree[MAXN<<2];
22 void build(int root,int l,int r){
23     L=l;R=r;
24     if(l==r)scanf("%d",&V);
25     else{
26         int mid=(l+r)>>1;
27         build(lson);
28         build(rson);
29         NOW;
30     }
31 }
32 void update(int root){
33     if(L==X&&R==X)V+=Y;
34     else{
35         int mid=(L+R)>>1;
36         if(mid>=X)update(root<<1);
37         else update(root<<1|1);
38         NOW;
39     }
40 }
41 void query(int root){
42     if(L>=X&&R<=Y)ans+=V;
43     else{
44         int mid=(L+R)>>1;
45         if(mid>=X)query(root<<1);
46         if(mid<Y)query(root<<1|1);
47     }
48 }
49 void input(){
50     char s[10];
51     int N,M;
52     scanf("%d%d",&N,&M);
53     build(1,1,N);
54     while(M--){
55         scanf("%s%d%d",s,&X,&Y);
56         if(!strcmp(s,"ADD"))update(1);
57         else{
58             ans=0;
59             query(1);
60             printf("%d
",ans);
61         }
62     }
63 }
64 int main(){
65     #ifdef LOCAL
66     freopen(data.in,"r",stdin);
67     freopen(data.out,"w",stdout);
68     #endif
69     input();
70     return 0;
71 }

树状数组：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAX(x,y)(x>y?x:y)
 7 #define MIN(x,y)(x<y?x:y)
 8 //#define LOCAL
 9 const int INF=0x3f3f3f3f;
10 const int MAXN=1000010;
11 int tree[MAXN];
12 int N;
13 int lowbit(int x){
14     return x&(-x);
15 }
16 void update(int x,int y){
17     while(x<=N){
18         tree[x]+=y;
19         x+=lowbit(x);
20     }
21 }
22 int query(int x){
23     int ans=0;
24     while(x){
25         ans+=tree[x];
26         x-=lowbit(x);
27     }
28     return ans;
29 }
30 int main(){
31     #ifdef LOCAL
32     freopen(data.in,"r",stdin);
33     freopen(data.out,"w",stdout);
34     #endif
35     int M;
36     scanf("%d%d",&N,&M);
37     int a,b;
38     for(int i=1;i<=N;i++){
39         scanf("%d",&a);
40         update(i,a);
41     }
42     char s[10];
43     while(M--){
44         scanf("%s",s);
45         scanf("%d%d",&a,&b);
46         if(!strcmp(s,"ADD"))update(a,b);
47         else
48         printf("%d
",query(b)-query(a-1));
49     }
50     return 0;
51 }