有关更深入的解释，请查看我的github存储库：https://github.com/VerisimilitudeX/LeetCode

直觉

问题是实现一个可以更新和查询给定矩形子部门的类。子区域由其四个角（Row1，Col1，Row2，Col2）定义。解决此问题的一种方法是存储原始矩形和同类中的更新列表。每个更新都包含子端口的坐标和新值以填充它。要查询给定位置的值（行，col），我们可以以相反顺序迭代更新，并检查位置是否属于任何子级别。如果是，我们返回相应的值。如果否，我们从矩形返回原始值。

方法

要实现此方法，我们需要两个数据结构：一个2D数组来存储原始矩形和一个以存储更新的列表。构造函数将矩形作为输入，并初始化数组和列表。更新的Ubrectangle方法将带有给定参数的新更新附加到列表中。 GetValue方法从末尾迭代遍历列表，并检查给定位置是否在任何更新中。如果是，它将从该更新中返回值。如果否，它将从数组返回值。

复杂

• 时间复杂性：
  构造函数的时间复杂性为$$ o（mn）$$，其中$$ m $$和$$ n $$分别是矩形的行数和列数。更新ubrectangle方法的时间复杂性为$$ o（1）$$，因为它仅附加到列表中。 getValue方法的时间复杂性是$$ o（k）$$，其中$$ k $$是列表中的更新数。

• 空间复杂性：
  该类的空间复杂性为$$ O（Mn + K）$$，其中$$ m $$，$$ n $$和$$ k $$定义为上述。我们需要$$ o（mn）$$空间来存储数组和$$ o（k）$$空间以存储列表。

代码

import java.util.*;

class SubrectangleQueries {
 private int[][] rect;
 private List<int[]> updates;

 public SubrectangleQueries(int[][] rectangle) {
 rect = rectangle;
 updates = new ArrayList<>();
 }

 public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
 updates.add(new int[]{row1, col1, row2, col2, newValue});
 }

 public int getValue(int row, int col) {
 for (int i = updates.size() - 1; i >= 0; i--) {
 int[] update = updates.get(i);
 if (row >= update[0] && row <= update[2] && col >= update[1] && col <= update[3]) {
 return update[4];
 }
 }
 return rect[row][col];
 }
}

我的leetcode解决方案：https://leetcode.com/VerisimilitudeX/