力扣1476-子矩形查询

摘要: 惰性更新与延迟计算的经典问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在很多数据结构中，对节点更新的时间复杂度是比 $O(1)$ 要大的。当修改非常频繁，但是查询相对稀少的时候，可以将修改操作记录下来，形成一个操作序列。等到查询的时候再集中处理操作序列，到时候操作序列中可能有很多修改操作可以抵消掉，从而减少修改操作。

这种惰性更新的思想在 Python 的惰性迭代器中也有所体现。利用函数式思维以及惰性迭代器可以写出简洁又高效的程序。比如 map 和 filter 函数可以返回惰性迭代器，reduce 可以传入惰性迭代器。另外，在 c++11 利用 std::function, lambda 表达式以及 Optional 实现惰性更新。

在文章 惰性更新 中我们简要学习了惰性更新的思想。本文我们看一个关于用惰性更新来应对多次单点查询的问题，力扣 1476，这是第 28 场双周赛 B 题。

$1 题目

• 1476. 子矩形查询

请你实现一个类 SubrectangleQueries ，它的构造函数的参数是一个 rows x cols 的矩形（这里用整数矩阵表示），并支持以下两种操作：

1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)

用 newValue 更新以 (row1,col1) 为左上角且以 (row2,col2) 为右下角的子矩形。

1. getValue(int row, int col)

返回矩形中坐标 (row,col) 的当前值。

提示：

最多有 500 次updateSubrectangle 和 getValue 操作。
1 <= rows, cols <= 100
rows == rectangle.length
cols == rectangle[i].length
0 <= row1 <= row2 < rows
0 <= col1 <= col2 < cols
1 <= newValue, rectangle[i][j] <= 10^9
0 <= row < rows
0 <= col < cols

示例 1：
输入：
[“SubrectangleQueries”,”getValue”,”updateSubrectangle”,”getValue”,”getValue”,”updateSubrectangle”,”getValue”,”getValue”]
[[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]]
输出：
[null,1,null,5,5,null,10,5]
解释：
SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]);
// 初始的 (4x3) 矩形如下：
// 1 2 1
// 4 3 4
// 3 2 1
// 1 1 1
subrectangleQueries.getValue(0, 2); // 返回 1
subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5);
// 此次更新后矩形变为：
// 5 5 5
// 5 5 5
// 5 5 5
// 5 5 5
subrectangleQueries.getValue(0, 2); // 返回 5
subrectangleQueries.getValue(3, 1); // 返回 5
subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10);
// 此次更新后矩形变为：
// 5 5 5
// 5 5 5
// 5 5 5
// 10 10 10
subrectangleQueries.getValue(3, 1); // 返回 10
subrectangleQueries.getValue(0, 2); // 返回 5

示例 2：
输入：
[“SubrectangleQueries”,”getValue”,”updateSubrectangle”,”getValue”,”getValue”,”updateSubrectangle”,”getValue”]
[[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]]
输出：
[null,1,null,100,100,null,20]
解释：
SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]);
subrectangleQueries.getValue(0, 0); // 返回 1
subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100);
subrectangleQueries.getValue(0, 0); // 返回 100
subrectangleQueries.getValue(2, 2); // 返回 100
subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20);
subrectangleQueries.getValue(2, 2); // 返回 20

---

$2 题解

算法：惰性更新

首先这是一个区间修改，多次单点查询的问题。区间修改常见的有三种：区间加，区间乘，区间赋值。

由于是区间赋值，最后输出 getValue 的结果只取决于最后一次操作，因此考虑惰性更新：将操作序列保存下来，查询时再看最后被赋的值是多少，将耗时操作推迟到不得不做的时候再做。

对于区间修改同时进行查询(单点/区间查询和/最值)问题，有线段树和树状数组这两个有力的数据结构，它们的区间修改也用到了惰性更新的特性，例如 699. 掉落的方块，用线段树维护区间赋值，维护区间最值，同时做区间查询。维护区间赋值时仍然惰性更新，参考 线段树：区间修改、区间查询，区间最值问题。

本题的区间修改是区间赋值，同时单点查询只是查询值，不涉及和与最值，并且由于是二维的所以最好不要用线段树把自己搞复杂了。最后输出 getValue 的结果只取决于最后一次操作，因此只要存储操作序列的参数，查询的时候从后往前顺序查看每个操作序列，查到的第一个修改范围包含查询坐标的即为答案。

本题是区间赋值，单点查询值，用到惰性更新。区间加，单点查询值也是一个常见需求，用的是差分的特性，而不是惰性更新。参考 力扣370-区间加法,差分。

代码(c++)

struct Op
{
    int x1, y1, x2, y2;
    int val;
    Op(int x1, int y1, int x2, int y2, int val):x1(x1),y1(y1),x2(x2),y2(y2),val(val){}
};

class SubrectangleQueries {
public:
    SubrectangleQueries(vector<vector<int>>& rectangle) {
        rec = rectangle;
        ops = vector<Op>();
    }

    void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        ops.push_back(Op(row1, col1, row2, col2, newValue));
    }

    int getValue(int row, int col) {
        int i = ops.size() - 1;
        while(i >= 0)
        {
            if(ops[i].x1 <= row && row <= ops[i].x2 && ops[i].y1 <= col && col <= ops[i].y2)
                return ops[i].val;
            --i;
        }
        return rec[row][col];
    }

private:
    vector<Op> ops;
    vector<vector<int>> rec;
};

---