nyoj123:这个题目是树状数组和线段树的简单题，一般来说树状数组能够结局的问题线段树都能够解决。树状数组编码极其简单。
下面是两个代码:
树状数组
/**//*
* 123.cpp
*
* Created on: 2013年8月12日
* Author: panzhizhou
*/
#include<iostream>
#include<string.h>
#include<cstring>
#include<stdio.h>
using namespace std;
//用树状数组来做
long long a[1000007];
int T,M;
int lowbit(int n)
{
return n&(-n);
}
void add(int pos,int value){
a[pos]+=value;
while(pos>0){
pos-=lowbit(pos);
a[pos]+=value;
}
}
int sum(int n){
long long _sum=0;
while(n<=M){
_sum+=a[n];
n+=lowbit(n);
}
return _sum;
}
int main(){
// string s;
//int v;
char s[10];
// memset(a,0,sizeof(a));
cin>>T>>M;
for(int i=0;i<T;i++){
// cin>>s;
scanf("%s",s);
if(s[0]=='A'){
int l,r,v;
// cin>>l>>r>>v;
scanf("%d%d%d",&l,&r,&v);
add(l-1,-v);
add(r,v);
}
else
{
int n;
scanf("%d",&n);
printf("%d\n",sum(n));
}
}
}
下面是线段树的代码：
/*
* 123_2.cpp
*
* Created on: 2013年8月13日
* Author: panzhizhou
*/
#include<iostream>
#include<string>
#include<stdio.h>
using namespace std;
typedef struct Node
{
int left;
int right;
int num;
}Node;
Node node[1000003<<2];
int T,M;
void build(int root,int l,int r){
node[root].left=l;
node[root].right=r;
node[root].num=0;
if(l<r) //最后一次如 2-3 ，就会产生2-2，3-3
{
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
}
}
void insert(int root,int b,int e,int v){
if(node[root].left>=b&&node[root].right<=e) //如果b,e包含当前root的范围，则可以插入搜索范围截止
{
node[root].num+=v;
return ;
}
int mid=(node[root].left+node[root].right)>>1;
if(e<=mid){
insert(root<<1,b,e,v);
}
else if(b>mid){ //右子树
insert(root<<1|1,b,e,v);
}
else
{
insert(root<<1,b,mid,v);
insert(root<<1|1,mid+1,e,v);
}
}
int Sum(int root,int x){
if(node[root].left==node[root].right){
return node[root].num;
}
int sum=node[root].num;
int mid=(node[root].left+node[root].right)>>1;
if(x<=mid){
sum+=Sum(root<<1,x);
}
else{
sum+=Sum(root<<1|1,x);
}
return sum;
}
int main()
{
//string s;
char s[11];
cin>>T>>M;
build(1,1,M);
for(int i=0;i<T;i++){
//cin>>s;
scanf("%s",s);
if(s[0]=='A'){
int l,r,v;
// cin>>l>>r>>v;
scanf("%d%d%d",&l,&r,&v);
insert(1,l,r,v);
}
else
{
int n;
// cin>>n;
scanf("%d",&n);
//cout<<Sum(1,n)<<endl;
printf("%d\n",Sum(1,n));
}
}
}