NYOJ 116 士兵杀敌(二) (线段树+树状数组)

#include <iostream>
#include <cstring>
#include <cstdio>
#define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
#define maxn 1000005
using namespace std;
int pre[maxn << 2];
int n,m;
char str[25];

void Pushup(int o){
  pre[o] = pre[o << 1] + pre[o << 1 | 1];
}

void Build(int l, int r, int o){
  if(l == r){
    scanf("%d",&pre[o]);
    return ;
  }
  int mid = (l + r) >> 1;
  Build(lson);
  Build(rson);
  Pushup(o);
}

void Update(int x,int ans,int l, int r,int o){
  if(l == r){
    pre[o] += ans;
    return ;
  }
  int mid = (l  + r) >> 1;
  if(x <= mid)Update(x,ans,lson);
  else Update(x,ans,rson);
  Pushup(o);
}

int Query(int L,int R,int l, int r, int o){
  if(L <= l && r <= R){
    return pre[o];
  }
  int ans = 0;
  int mid = (l + r) >> 1;
  if(L <= mid)ans += Query(L,R,lson);
  if(R > mid)ans += Query(L,R,rson);
  return ans;
}

int main()
{
  scanf("%d%d",&n,&m);
  Build(1,n,1);
  while(m--){
    scanf("%s",str);
    if(str[0] == 'A'){
      int x,y;
      scanf("%d%d",&x,&y);
      Update(x,y,1,n,1);
    }
    else{
      int x,y;
      scanf("%d%d",&x,&y);
      printf("%d\n",Query(x,y,1,n,1));
    }
  }
  return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1000005
using namespace std;
int pre[maxn];
char str[105];
int n,m;
 
int lowbit(int x){
  return x & (-x);
}
 
void Add(int x,int y){
  for(int i=x;i<=n;i+=lowbit(i)){
    pre[i] += y;
  }
}
 
int Query(int x){
  int sum = 0;
  for(int i=x;i>=1;i-=lowbit(i)){
    sum +=pre[i];
  }
  return sum;
}
 
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++){
    int index;
    scanf("%d",&index);
    Add(i, index);
  }
  while(m--){
    scanf("%s",str);
    if(str[0] == 'A'){
      int x,y;
      scanf("%d%d",&x,&y);
      Add(x, y);
    }
    else{
      int x,y;
      scanf("%d%d",&x,&y);
      printf("%d\n",Query(y) - Query(x-1));
    }
  }
  return 0;
}