题解：SP1029 MATSUM - Matrix Summation

· · 题解

upd on 2025/10/4：更正了一些下标问题。

前言

蒟蒻最近刚刚学了二维数组模板，于是找到此题作为再次熟悉。

题目大意

给定 n 组数据，每组数据给定一个初值为空且大小为 N \times N 的矩阵，并给出若干次操作，操作分为 SET 命令与 SUM 命令，分别表示将矩阵中的某个点改为某个值与查询其中一个子矩阵的和。

题目分析

明显不能进行暴力修改与查询，考虑更高效的维护方式，容易想到利用二维树状数组进行维护。

二维树状数组

本质的原理与一位树状数组区别不大，类比得到如下定义：定义 c_{x,y} 为一个以 a_{x,y} 为右下角，宽为 lowbit(x)，长为 lowbit(y) 的矩阵的总信息。

之后的修改与查询操作中，修改操作被实现为：

void add(int x, int y, int v) {
    for (int i=x; i <= n; i += lowbit(i)) {
        for (int j=y; j<=n; j += lowbit(j)) {
            c[i][j] += v;
        }
    }
}

其中正确性的证明参考此处。

而查询操作的原理可以类比二维前缀和的查询操作，即如下两个实现步骤：

int sum(int x,int y) {
    int ret=0;
    for(int i=x; i; i-=lowbit(i)) {
        for(int j=y; j; j-=lowbit(j)) {
            ret+=c[i][j];
        }
    }
    return ret;
}
int sum_(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);
}

正确性的证明依旧参考此处。

代码

而后给出本题完整的代码，注意多测清空。

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ri register int
#define int long long
#define lowbit(x) x&-x
using namespace std;
const int N=1e3+30;
int a[N][N],T;
int n;
struct b1t {
    int c[N][N];
    void add(int x, int y, int v) {
        for (int i=x; i <= n; i += lowbit(i)) {
            for (int j=y; j<=n; j += lowbit(j)) {
                c[i][j] += v;
            }
        }
    }
    int sum(int x,int y) {
        int ret=0;
        for(int i=x; i; i-=lowbit(i)) {
            for(int j=y; j; j-=lowbit(j)) {
                ret+=c[i][j];
            }
        }
        return ret;
    }
    int sum_(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);
    }
} t;
signed main() {
    IOS
    cin>>T;
    while(T--) {
        cin>>n;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                a[i][j]=0;
                t.c[i][j]=0;
            }
        }
        string op;
        while(cin>>op and op!="END") {
            if(op=="SET") {
                int x,y,val;
                cin>>x>>y>>val;
                x++,y++;
                t.add(x,y,val-a[x][y]);
                a[x][y]=val;
            } else {
                int x1,y1,x2,y2;
                cin>>x1>>y1>>x2>>y2;
                x1++,y1++,x2++,y2++;
                cout<<t.sum_(x1,y1,x2,y2)<<endl;
            }
        }
    }
    return 0;
}