P2068 统计和

题目描述

给定一个长度为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：

54x 3 8y 1 3x 4 9y 3 4

输出样例#1：

817 线段树单点修改区间查询

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define N 410000using namespace std;char ch;int n,m,x,y,ans;int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}struct Tree{    int l,r,w,f; }tree[N];void build(int k,int l,int r){    tree[k].l=l,tree[k].r=r;    if(tree[k].l==tree[k].r)    {        tree[k].w=0;        return ;    }    int m=(l+r)>>1;    build(k<<1,l,m);    build(k<<1|1,m+1,r);}void change_point(int k){    if(tree[k].l==tree[k].r)    {        tree[k].w+=y;        return ;    }    int m=(tree[k].r+tree[k].l)>>1;    if(x<=m) change_point(k<<1);    else change_point(k<<1|1);    tree[k].w=tree[k<<1].w+tree[k<<1|1].w;}void ask_interval(int k){    if(tree[k].l>=x&&tree[k].r<=y)    {        ans+=tree[k].w;        return ;    }    int m=(tree[k].r+tree[k].l)>>1;    if(x<=m) ask_interval(k<<1);    if(y>m)  ask_interval(k<<1|1);}int main(){    n=read(),m=read();    build(1,1,n);    while(m--)    {        ans=0;        cin>>ch;x=read(),y=read();        if(ch=='x')         change_point(1);        else         {            ask_interval(1);            printf("%d\n",ans);        }    }    return 0;}