【洛谷 2068】统计和

你的名字 2021-10-19 11:28 319阅读 0赞

## 题目描述 ##

给定一个长度为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
    
    线段数做法：

// luogu-judger-enable-o2
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    #include<cmath>
    #define maxn 100007 
    using namespace std;
    int n,m,x,y,z;
    char jjj[4];
    long long Sum[maxn<<2],Add[maxn<<2];
    int A[maxn];
    
    void PushUp(int rt){Sum[rt]=Sum[rt*2]+Sum[rt*2+1];}
    
    void Build(int l,int r,int rt){
        if(l==r) {
            Sum[rt]=A[l];
            return;
        }
        int m=(l+r)>>1;
        Build(l,m,rt<<1);
        Build(m+1,r,rt<<1|1);
        PushUp(rt);
    }
    void PushDown(int rt,int ln,int rn){
        if(Add[rt]){
            Add[rt<<1]+=Add[rt];
            Add[rt<<1|1]+=Add[rt];
            Sum[rt<<1]+=Add[rt]*ln;
            Sum[rt<<1|1]+=Add[rt]*rn;
            Add[rt]=0;
        }
    }
    long long Query(int L,int R,int l,int r,int rt){
        if(L <= l && r <= R)
            return Sum[rt];
        int m=(l+r)>>1;
        PushDown(rt,m-l+1,r-m); 
        long long ANS=0;
        if(L <= m) ANS+=Query(L,R,l,m,rt<<1);
        if(R >  m) ANS+=Query(L,R,m+1,r,rt<<1|1);
        return ANS;
    } 
    
    void Update(int L,int R,int C,int l,int r,int rt){
        if(L <= l && r <= R){
            Sum[rt]+=C*(r-l+1);
            Add[rt]+=C;
            return ; 
        }
        int m=(l+r)>>1;
        PushDown(rt,m-l+1,r-m);
        if(L <= m) Update(L,R,C,l,m,rt<<1);
        if(R >  m) Update(L,R,C,m+1,r,rt<<1|1); 
        PushUp(rt);
    } 
    
    int main(){
        while(scanf("%d%d",&n,&m)!=EOF){
            for(int i=1;i<=n;i++)
                A[i]=0;
            Build(1,n,1);
            while(m--)
            {
                scanf("%s",jjj);
                if(jjj[0]=='x') {
                    scanf("%d%d",&x,&z);
                    Update(x,x,z,1,n,1);
                }
                else {
                    scanf("%d%d",&x,&y);
                    printf("%lld\n",Query(x,y,1,n,1));
                }
            }
        }
        return 0;
    }

树状数组解法如下：

’

#include<iostream>
    using namespace std;
    const int MAXN=100000+2;
    int a[MAXN];
    int n,w;
    int lowbit(int x){
        return x&(-x);
    }
    void add(int p,int x){
        while(p<=n){
            a[p]+=x;
            p+=lowbit(p);
        }
    }
    int ask(int p){
        int ans=0;
        while(p>0){
            ans+=a[p];
            p-=lowbit(p);
        }
        return ans;
    }
    int main(){
        cin>>n>>w;
        for(int i=1;i<=w;i++){
            char q;
            int y,z;
            cin>>q>>y>>z;
            if(q=='x') add(y,z);
            else cout<<ask(z)-ask(y-1)<<endl;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11205996.html