单点增加,范围查询

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

void add(int i,int v){
    while(i<=n){
        a[i]+=v;
        i+=lowbit(i);
    }
}

int query(int i){
    int res=0;
    while(i>0){
        res+=a[i];
        i-=lowbit(i);
    }
    return res;
}

单点查询,范围增加

存储原数组的差分数组即可

单点查询,范围增加

维护两个差分信息 d和(i-1)*d
sum=k*d(l,r)-(i-1)*d

二维范围查询,范围修改

int n,m;
int d1[2050][2050],d2[2050][2050],d3[2050][2050],d4[2050][2050];

inline int lowbit(int x){
    return x&-x;
}
void add(int x,int y,int v){
    int v1=v,v2=x*v,v3=y*v,v4=x*y*v;
    for(int i=x;i<=n;i+=lowbit(i)){
        for(int j=y;j<=m;j+=lowbit(j)){
            d1[i][j]+=v1;
            d2[i][j]+=v2;
            d3[i][j]+=v3;
            d4[i][j]+=v4;
        }
    }
}

void add(int a,int b,int c,int d,int v){
    add(a,b,v);
    add(a,d+1,-v);
    add(c+1,b,-v);
    add(c+1,d+1,v);
}

int query(int x,int y){
    int res=0;
    for(int i=x;i>0;i-=lowbit(i)){
        for(int j=y;j>0;j-=lowbit(j)){
            res+= (x + 1) * (y + 1) * d1[i][j] 
            - (y + 1) * d2[i][j] 
            - (x + 1) * d3[i][j] 
            + d4[i][j];
        }
    }
    return res;
}

int sum(int a, int b, int c, int d) {
    return query(c, d) - query(a - 1, d) - query(c, b - 1) + query(a - 1, b - 1);
}