题目传送门

P4514 上帝造题的七分钟 - 洛谷

题目简述

初始有一个 n×m 的全零矩阵，需要支持两种操作：

  1. 矩形加法：将左上角 (a,b)、右下角 (c,d) 的矩形区域内的所有数加上 delta。

  2. 矩形求和：查询左上角 (a,b)、右下角 (c,d) 的矩形区域内所有数的和。

操作数量较多，需要高效实现，时间复杂度约为 O(log⁡nlog⁡m) 每次操作

思路分析

本题是典型的 二维区间修改 + 区间查询 问题。若直接使用二维树状数组维护原矩阵，区间加法需要修改矩形内所有元素，复杂度不可接受。因此引入 二维差分 将区间修改转化为四个单点修改，而区间查询则通过维护差分数组的加权前缀和来实现。

二维差分

设原矩阵为 a[i][j]，其二维差分数组 d[i][j] 定义为：

对矩形 [a..c]×[b..d] 整体加 delta，只需修改差分数组的四个角：

d[a][b]     += delta
d[c+1][b]   -= delta
d[a][d+1]   -= delta
d[c+1][d+1] += delta

这样，求一次二维前缀和后，矩形内部的每个元素都会增加 delta，其余位置不变。

前缀和与四个树状数组

我们的目标是快速查询任意矩形和，也就是求原矩阵的二维前缀和：

将 a[i][j] 用差分数组表示并交换求和顺序：

其中 (x−p+1)(y−q+1) 是差分点 (p,q) 影响到的格子数量。展开该乘积：

(x−p+1)(y−q+1)=(x+1)(y+1)−(y+1) p−(x+1) q+p 

代入并整理得到：

因此，如果我们能快速求出以下四个量和：

  1. ∑d[p][q]

  2. ∑d[p][q]⋅p

  3. ∑d[p][q]⋅q

  4. ∑d[p][q]⋅p⋅q

就可以在 O(log⁡nlog⁡m) 时间内得到前缀和。于是我们维护 四个二维树状数组：

数组

存储内容

t1

∑d

t2

∑d⋅x（x 为差分点行坐标）

t3

∑d⋅y（y 为差分点列坐标）

t4

∑d⋅x⋅y

每次更新差分点 (x,y) 加上 d 时，同步更新四个树状数组：

  • t1 加 d

  • t2 加 d * x

  • t3 加 d * y

  • t4 加 d * x * y

这样，查询时利用四个树状数组分别求出对应的区间和，套用公式即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define maxn 3000

int n, m;
vector<vector<int>> t1(maxn, vector<int>(maxn));
vector<vector<int>> t2(maxn, vector<int>(maxn));
vector<vector<int>> t3(maxn, vector<int>(maxn));
vector<vector<int>> t4(maxn, vector<int>(maxn));

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

void update(int x, int y, int d) {
    for (int i = x; i <= n; i += lowbit(i)) {
        for (int j = y; j <= m; j += lowbit(j)) {
            t1[i][j] += d, t2[i][j] += d * x;
            t3[i][j] += d * y, t4[i][j] += d * y * x;
        }
    }
}

int sum(int x, int y) {
    int h = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        for (int j = y; j > 0; j -= lowbit(j)) {
            h += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
        }
    }
    return h;
}

void solve() {
    char X;
    cin >> X >> n >> m;
    char p;
    while (cin >> p) {
        if (p == 'L') {
            int a, b, c, d, delta;
            cin >> a >> b >> c >> d >> delta;
            //四个角
            update(c + 1, d + 1, delta);
            update(a, b, delta);
            update(c + 1, b, -delta);
            update(a, d + 1, -delta);
        }
        else {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            cout << sum(c, d) + sum(a - 1, b - 1) - sum(c, b - 1) - sum(a - 1, d) << endl;
        }
    }
}

 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

总结

本题通过二维差分将区间修改转换为四次单点修改，再利用四个树状数组分别维护差分值及其坐标加权和，实现了高效的二维区间修改与区间查询。