树状数组模板

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1000 + 5;
 4 int C[maxn], n;
 5 
 6 int lowbit(int x) {return x & -x;}
 7 
 8 int sum(int x) {
 9     int ret = 0;
10     while(x) {
11         ret += C[x]; x -= lowbit(x);
12     }
13     return ret;
14 }
15 
16 void add(int x, int d) {
17     while(x <= n) {
18         C[x] += d; x += lowbit(x);
19     }
20 }
21 
22 int get_sum(int L, int R) {
23     return sum(R) - sum(L-1);
24 }
25 
26 int main() {
27     int q, d;
28     while(cin >> n >> q) {
29         memset(C, 0, sizeof(C));
30         for (int i = 1; i <= n; ++i) {
31             cin >> d;
32             add(i, d);
33         }
34         int qL, qR;
35         while(q--) {
36             cin >> qL >> qR;
37             cout << get_sum(qL, qR) << endl;
38         }
39     }
40 
41     return 0;
42 }