HDU-1166 敌兵布阵 (树状数组模板题——单点更新，区间求和）

• 2020 年 2 月 24 日
• 笔记

AC代码：

#include<iostream>  #include<cstdio>  #include<cstring>  #include<algorithm>  #include<bitset>  #include<cassert>  #include<cctype>  #include<cmath>  #include<cstdlib>  #include<ctime>  #include<deque>  #include<iomanip>  #include<list>  #include<map>  #include<queue>  #include<set>  #include<stack>  #include<vector>  #define mp make_pair  #define pi acos(-1)  #define pii pair<int, int>  #define pll pair<long long , long long>  #define ll long long  #define ld long double  #define MEMS(x) memset(x, -1, sizeof(x))  #define MEM(x) memset(x, 0, sizeof(x))  #define lowbit(x) x&(-x)  const int inf = 0x3f3f3f3f;  const int maxn = 50001;  using namespace std;  int T, N, c[maxn];  char order[maxn];  void update(int x, int y)  {      for(int i = x; i <= N; i += lowbit(i))          c[i] += y;  }  int getsum(int x)  {      int ans = 0;      while(x)      {          ans += c[x];          x -= lowbit(x);      }      return ans;  }  int main()  {  //    freopen("input.txt", "r", stdin);  //    freopen("output.txt", "w", stdout);      scanf("%d", &T);      for(int t = 1; t <= T; t++)      {          scanf("%d", &N);          memset(c, 0, sizeof(c));          for(int i = 1; i <= N; i++)          {              int a;              scanf("%d", &a);              update(i, a);          }          printf("Case %d:n", t);          while(scanf("%s", order) != EOF)          {              if(!strcmp(order, "End"))                  break;              if(!strcmp(order, "Add"))              {                  int i, j;                  scanf("%d %d", &i, &j);                  update(i, j);              }              else if(!strcmp(order, "Sub"))              {                  int i, j;                  scanf("%d %d", &i, &j);                  update(i, -j);              }              else if(!strcmp(order, "Query"))              {                  int i, j;                  scanf("%d %d", &i, &j);                  printf("%dn", getsum(j) - getsum(i - 1));              }          }      }    }