1 /* 2     线段树基本功能：区间值的和，修改某个值 3 */ 4 #include 
     
       5 #include 
      
        6 #define lson l, m, rt << 1 7 #define rson m+1, r, rt << 1|1 8  9 const int MAX_N = 50000 + 10;10 int sum[MAX_N<<2];11 12 void pushup(int rt)            //杭电大牛：notOnlySuccess 版本13 {14     sum[rt] = sum[rt<<1] + sum[rt<<1|1];15 }16 17 void build(int l, int r, int rt)18 {19     if (l == r)20     {21         scanf ("%d", &sum[rt]);22         return ;23     }24     int m = (l + r) >> 1;25     build (lson);26     build (rson);27     pushup (rt);28 }29 30 void update(int p, int add, int l, int r, int rt)31 {32     if (l == r)33     {34         sum[rt] += add;35         return ;36     }37     int m = (l + r) >> 1;38     if (p <= m)    update (p, add, lson);39     else    update  (p, add, rson);40     pushup (rt);41 }42 43 int query(int ql, int qr, int l, int r, int rt)44 {45     if (ql <= l && r <= qr)46     {47         return sum[rt];48     }49     int m = (l + r) >> 1;50     int ans = 0;51     if (ql <= m)    ans += query (ql, qr, lson);52     if (qr > m)        ans += query (ql, qr, rson);53     54     return ans;55 }56 57 int main(void)            //HDOJ 1166 敌兵布阵58 {59     //freopen ("inA.txt", "r", stdin);60     int t, n, cas, ans;61     int b, c;62     char s[10];63     64     while (~scanf ("%d", &t))65     {66         cas = 0;67         while (t--)68         {69             scanf ("%d", &n);70             build (1, n, 1);71             printf ("Case %d:\n", ++cas);72             while (~scanf ("%s", &s))73             {74                 if (strcmp (s, "End") == 0)    break;75                 scanf ("%d%d", &b, &c);76                 if (strcmp (s, "Query") == 0)77                 {78                     ans = query (b, c, 1, n, 1);79                     printf ("%d\n", ans);80                 }81                 else if (strcmp (s, "Add") == 0)82                 {83                     update (b, c, 1, n, 1);84                 }85                 else if (strcmp (s, "Sub") == 0)86                 {87                     update (b, -c, 1, n, 1);88                 }89             }90         }    91     }92     93     return 0;94 }
      
     

1 /* 2     树状数组 3 */ 4 #include 
      
        5 #include 
       
         6  7 const int MAX_N = 50000 + 10; 8 int a[MAX_N]; 9 int n, num;10 11 int lowbit(int t)        //求 2^k12 {13     //return t & (t ^ (t - 1));14     return t & (-t);15 }16 17 void plus(int num, int x)        //第i个增加num个人18 {19     while (x <= n)20     {21         a[x] += num;22         x += lowbit (x);23     }24 }25 26 int sum(int x)            //求前x项的和27 {28     int sum = 0;29     while (x > 0)30     {31         sum += a[x];32         x -= lowbit(x);33     }34     return sum;35 }36 37 int main(void)38 {39     //freopen ("inA.txt", "r", stdin);40 41     int t;42     char op[100];43 44     scanf ("%d", &t);45     int k = t;46 47     while (k--)48     {49         memset (a, 0, sizeof (a));50         scanf ("%d", &n);51         for (int i=1; i<=n; ++i)52         {53             scanf ("%d", &num);54             plus (num, i);55         }56         int r = 1;57         while (scanf ("%s", &op), op[0] != 'E')58         {59             int a, b;60             scanf ("%d%d", &a, &b);61             switch (op[0])62             {63                 case 'A':64                     plus (b, a);65                     break;66                 case 'S':67                     plus (-b, a);68                     break;69                 case 'Q':70                     if (r)71                         printf ("Case %d:\n", t - k);72                     r = 0;73                     printf ("%d\n", sum (b) - sum (a-1));74                     break;75             }76         }77     }78 79     return 0;80 }