树状数组-区间查询算法

原题 P3368

与P3374大同小异，不过树状数组$t$[500002]使用差分进行优化。

差分原理

若有一个数组$a$，则它的差分数组为$t$。

那么$t[i]=a[i]+a[i-1]$ （初始化）

且$a[i]=t[1]+t[2]+···+t[i]$（使用）

当在$a[i]-a[j]$之间进行区间$+v$时，

则$t[i]+=v$，$t[j]-=v$即可。

#include<bits/stdc++.h>
int t[500002],n,m;
int lowbit(int k){return k&-k;}
void add(int x,int y){
    while(x<=n){
        t[x]+=y;
        x+=lowbit(x);
    }
    return;
}
int sum(int y){
    int y_sum=0;
    while(y){
        y_sum+=t[y];
        y-=lowbit(y);
    }
    return y_sum;
}
int main(){
    int a,ba;
    scanf("%d%d",&n,&m);
    for(int i(1);i<=n;i++) {
        scanf("%d",&a);
        add(i,a-ba);
        ba=a;
    }
    for(int i(1);i<=m;i++){
        int c,x,y,v,s;
        scanf("%d",&c);
        if(c==1){
            scanf("%d%d%d",&x,&y,&v);
            add(x,v); add(y+1,-v);
        }else{
            scanf("%d",&s);
            printf("%d\n",sum(s));
        }
    }
    return 0;
}