NYOJ 123 士兵杀敌(四) (线段树+树状数组)

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

void Build(int l,int r,int o){
	lsum[o] = l;
	rsum[o] = r;
	sum[o] = 0;
	if(l == r)return ;
	int mid = (l + r) >> 1;
	Build(lson);
	Build(rson);
}

void Update(int L,int R,int ans,int o){
	if(L <= lsum[o] && rsum[o] <= R){
		sum[o] += ans;
		return ;
	}
	int mid = (lsum[o] + rsum[o]) >> 1;
	if(L > mid)Update(L,R,ans,o << 1 | 1);
	else if(R <= mid)Update(L,R,ans,o << 1);
	else{
		Update(L,mid,ans,o<<1);
		Update(mid+1,R,ans,o<<1|1);
	}
}

int Query(int x,int o){
	if(lsum[o] == x && rsum[o] == x){
		return sum[o];
	}
	int mid = (lsum[o] + rsum[o]) >> 1;
	int ans = sum[o];
	if(x <= mid)ans += Query(x,o << 1);
	else ans += Query(x,o << 1 | 1);
	return ans;
}

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

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1000005
using namespace std;
int pre[maxn];
char str[10];
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",&m,&n);
  while(m--){
    scanf("%s",str);
    if(str[0] == 'A'){
      int x,y,z;
      scanf("%d%d%d",&x,&y,&z);
      Add(x, z);
      Add(y + 1, -z);
    }
    else{
      int x;
      scanf("%d",&x);
      printf("%d\n",Query(x));
    }
  }
  return 0;
}