题目描述
给定一个长度为n（n<=100000），初始值都为0的序列，x(x<=10000)次的修改某些位置上的数字，每次加上一个数，然后提出y (y<=10000)个问题，求每段区间的和。时间限制1秒。
输入输出格式
输入格式：
第一行1个数，表示序列的长度n
第二行1个数，表示操作的次数w
后面依次是w行，分别表示加入和询问操作
其中，加入用x表示，询问用y表示
x的格式为"x a b" 表示在序列a的位置加上b
y的格式为"y a b" 表示询问a到b区间的加和
输出格式：
每行一个数，分别是每次询问的结果
输入输出样例
输入样例#1：
5 4 x 3 8 y 1 3 x 4 9 y 3 4
输出样例#1：
代码
8 17
1 /* 2 竟然是读入字符出错 3 一开始用的%c 可能会读入空格 4 改为char数组就好了 5 线段树单点修改和区间查询 6 */ 7 #include<cstdio> 8 #include<iostream> 9 #define MAXN 100010 10 11 using namespace std; 12 13 int n,m,y,z; 14 15 char x[5]; 16 17 int tree[MAXN*4]; 18 19 inline void read(int &x) { 20 int f=1;x=0;char c=getchar(); 21 while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} 22 while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-48;c=getchar();} 23 x=x*f; 24 } 25 inline void build(int now,int l,int r) { 26 if(l==r) { 27 tree[now]=0; 28 return; 29 } 30 int mid=(l+r)>>1; 31 build(now<<1,l,mid); 32 build(now<<1|1,mid+1,r); 33 tree[now]=tree[now<<1]+tree[now<<1|1]; 34 } 35 36 inline void __ADD(int now,int l,int r,int p,int val) { 37 if(l==r) { 38 tree[now]+=val; 39 return; 40 } 41 int mid=(l+r)>>1; 42 if(p<=mid) __ADD(now<<1,l,mid,p,val); 43 else if(p>mid) __ADD(now<<1|1,mid+1,r,p,val); 44 tree[now]=tree[now<<1]+tree[now<<1|1]; 45 } 46 47 inline int query(int now,int l,int r,int p,int q) { 48 if(l==p&&r==q) return tree[now]; 49 int mid=(l+r)>>1; 50 if(p>mid) return query(now<<1|1,mid+1,r,p,q); 51 else if(q<=mid) return query(now<<1,l,mid,p,q); 52 else return query(now<<1,l,mid,p,mid)+query(now<<1|1,mid+1,r,mid+1,q); 53 } 54 55 int main() { 56 read(n);read(m); 57 build(1,1,n); 58 for(int i=1;i<=m;i++) { 59 scanf("%s",x); 60 if(x[0]=='x') { 61 read(y);read(z); 62 __ADD(1,1,n,y,z); 63 } 64 else if(x[0]=='y') { 65 read(y);read(z); 66 int ans=query(1,1,n,y,z); 67 printf("%d ",ans); 68 } 69 } 70 return 0; 71 }