NYOJ 108 士兵杀敌（一）

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

线段树，或者树状数组

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     scanf("%d%d",&n,&m);
30     for(i=1;i<=n;i++)
31     {
32         scanf("%d",&a);
33         mod(i,a);
34     }
35     while(m--)
36     {
37         scanf("%d%d",&a,&b);
38         printf("%d\n",getSum(b)-getSum(a-1));
39     }
40     return 0;
41 }