看心情填坑

下午的脑洞。

太久没更了更个东西凑数

支持单点修改区间求和的树状数组

支持区间修改单点查询的树状数组

这两个东西太傻不讲。

假设现在我们有一个k维空间，规模为n，我们现在要支持区域求和区域加减。

现在以两维为例。

显然query(x1,y1,x2,y2)=sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)，多维也可以容斥道理是一样的。

为了方便我们假设原来每一个位置都是0假如原矩阵有的直接前缀和搞一下就可以了。

定义：

d_i,j表示左上角为i,j，右下角为n,n的矩阵计算答案是都要+d_i,j。

然后显然我们可以通过维护d_i,j来得出答案,d_i,j,$sum(x,y)=\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]*(x+1-i)*(y+1-j)$

d_i,j对答案贡献了(x+1-i)*(y+1-j)次所以可以这样算，把这个东西拆一下，就是$d[i][j]*(x+1)*(y+1)-d[i][j]*(x+1)*j-d[i][j]*i*(y+1)+d[i][j]*i*j $

我们只要维护d[i][j]*i*j,d[i][j]*i,d[i][j]*j,d[i][j]这4个东西就可以了。

这个东西可以推广到k维，需要2^k个树状数组维护，2位的懂了k位的也不难写。

总复杂度时间O((n*log(n)*2)^k)空间O((n*2)^k)一维和两维比线段树写法跑得快，三维以上没试过。

写法理解之后还是蛮好写的，常数也蛮小的其实并没有什么卵用

#include<cstdio>
using namespace std;
char c[10];
int n,m,x1,x2,y1,y2,x;
int tree[2050][2050][2][2];
inline int read(){
    int p=1,x;char c;
    while((c=getchar())<'0'||c>'9')if(c=='-')p=-1;
    x=c-'0';
    while((c=getchar())>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0';
    x*=p;
    return x;
}
int lowbit(int k){return k&-k;}
int Sum(int x,int y,int k1,int k2){
    long long ans=0;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))ans+=tree[i][j][k1][k2];
    return ans;
}
void Add(int x,int y,int a,int k1,int k2){
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=m;j+=lowbit(j))tree[i][j][k1][k2]+=a;
}
void add(int x,int y,int k){
    Add(x,y,k,0,0);
    Add(x,y,k*x,1,0);
    Add(x,y,k*y,0,1);
    Add(x,y,k*x*y,1,1);
}
int sum(int x,int y){
    return Sum(x,y,0,0)*(x+1)*(y+1)-Sum(x,y,0,1)*(x+1)-Sum(x,y,1,0)*(y+1)+Sum(x,y,1,1);
}
int main(){
    c[0]=getchar();
    n=read();m=read();
    while(scanf("%s",c)!=EOF){
        if(c[0]=='k'){
            x1=read();y1=read();x2=read();y2=read();
            printf("%d\n",sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1));
        }else{
            x1=read();y1=read();x2=read();y2=read();x=read();
            add(x1,y1,x);add(x2+1,y1,-x);add(x1,y2+1,-x);add(x2+1,y2+1,x);
        }
    }

}

嘛，我代码风格比较差，总的来说这个东西性价比还是蛮高的

晚上开GYM写题解