【题解】Luogu P2068 【统计和】

这题问单点修改,求区间和,单点修改可用树状数组,区间和可表示为前缀和的差的形式,如:$\sum_{i=l}^{r}=ask(r)-ask(l-1)$。

#include<cstdio>

const int MAXN = 100000 + 6;
int c[MAXN],n;

inline int lowbit(int x){
    return x & -x;
}

int ask(int x){
    int ans = 0;
    for(;x;x -= lowbit(x)){
        ans += c[x];
    }
    return ans;
}

void add(int x,int y){
    for(;x <= n;x += lowbit(x)){
        c[x] += y;
    }
}

int main(){
    int w;
    scanf("%d\n%d\n",&n,&w);
    
    for(int i = 0;i < w;i++){
        char op;
        int a,b;
        scanf("%c %d %d\n",&op,&a,&b);
        if(op == 'x'){
            add(a,b);
        }else if(op == 'y'){
            printf("%d\n",ask(b) - ask(a - 1));
        }
    }
    
    return 0;
}

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注