树状数组-区间查询算法

原题 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;
}