NYOJ 116 士兵杀敌（二）

http://acm.nyist.net/JudgeOnline/problem.php?pid=116

和士兵杀敌（一）是一样的。

View Code

 1 #include <iostream>
 2 #include <stdio.h>
 3 using namespace std;
 4 const int maxn = 1000005;
 5 int ans[maxn], n;
 6 int lowbit(int x)
 7 {
 8     return x & (-x);
 9 }
10 
11 int getSum(int x)
12 {
13     int i, sum=0;
14     for(i = x; i > 0; i-=lowbit(i))
15     sum += ans[i];
16     return sum;
17 }
18 
19 int mod(int x, int num)
20 {
21     int i;
22     for(i = x; i <= n; i+=lowbit(i))
23     ans[i] += num;
24 }
25 
26 int main()
27 {
28     int m, i, j, a, b;
29     char s[30];
30     scanf("%d%d",&n,&m);
31     for(i=1;i<=n;i++)
32     {
33         scanf("%d",&a);
34         mod(i,a);
35     }
36     while(m--)
37     {
38         scanf("%s%d%d",s,&a,&b);
39         if(s[0]=='Q') printf("%d\n",getSum(b)-getSum(a-1));
40         else mod(a,b);
41     }
42     return 0;
43 }