优美的二维树状数组

有一类求一段区间内所有数字的和的问题，以前我是用前缀和数组解决的。
今天遇到了二维的树状数组，发现它的代码非常优美，就把这两者一起写一写吧。

1. 一维前缀和数组

假设共有n个数字，我们把它们存放在a数组中

for (int i=1;i<=n;i++)
    std::cin>>a[i];

然后，我们用sum[i]表示a[1]+a[2]+…+a[i],
显然sum[i]=sum[i-1]+a[i];
很容易就求出了前缀和数组

sum[0]=0;
for (int i=1;i<=n;i++)
    sum[i]=sum[i-1]+a[i]

当我们要计算l到r闭区间内的所有数字的和时，可以用sum[r]-sum[l-1]求出

int getSum(int l,int r){
    return sum[r]-sum[l-1];
}

2. 二维前缀和数组

如果我们的数字一共有n行m列，想求从左上角(x1,y1)到右下角(x2,y2)的矩形内的数字的和，也可以使用前缀和。
我们把数字存放在a[i][j]中,从(1,1)到(i,j)的矩形内数字的和存放在sum[i][j]中

for (int i=1;i<=n;i++){
    for (int j=1;j<=n;j++){
        std::cin>>a[i][j];
        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    }
}

为什么这样写？自己在草稿本上画一下图就明白了。
求和也非常简单

int getSum(int x1,int y1,int x2,int y2){
    return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}

前缀和数组预处理的时间复杂度是O(nm)，查询的时间复杂度是O(1),非常快。
但是它有一个缺点就是修改很慢，每次修改一个点就要修改这个点后面的sum数组，时间复杂度是O(nm)

3. 一维树状数组

树状数组查询和修改的时间都是O(log(n)),当有大量的修改时，我们应该使用树状数组
注意，这里的sum与前缀和中的sum不同

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

void add(int x,int v){
//修改操作，给a[x]加上v
    for (int i=x;i<=n;i+=lowbit(i))
        sum[i]+=v;
}

int getSum(int x){
//查询a[1]+a[2]+...+a[x]的和
    int ans = 0;
    for (int i=x;i;i-=lowbit(i))
        ans+=sum[i];
    return ans; 
}

int getSum(int l,int r){
//查询a[l]+a[l+1]+...+a[r]的和
    return getSum(r)-getSum(l-1);
}

可以看到，两者的getSum非常像

3. 二维树状数组

二维树状数组简直就是一维树状数组和二维前缀和数组结合起来，查询的代码一模一样

const int maxn = 305;

struct STree {
 
    int a[maxn][maxn];

    int lowbit(int x){
        return (-x)&x;
    }
    
    void add(int x,int y,int v){
        for (int i=x;i<maxn;i+=lowbit(i)){
            for (int j=y;j<maxn;j+=lowbit(j)){
                a[i][j]+=v;
            }
        }
    }
    
    int query(int x,int y){
        int ans = 0;
        for (int i=x;i;i-=lowbit(i)){
            for (int j=y;j;j-=lowbit(j)){
                ans += a[i][j];
            }
        }
        return ans;
    }

    int query(int x1,int y1,int x2,int y2){
        return query(x2,y2) - query(x2,y1-1) - query(x1-1,y2) + query(x1-1,y1-1);
    }
 
};