algorithm - 如何有效地找到网格中某个范围内的元素总和？

Question

给定一个 n × n 正数网格，要获得由角描述的范围内的元素之和，可以达到的最佳复杂度是多少区域的矩形被认为是 (x1,y1) 和 (x2,y2)？会有q这样的查询。

PS:考虑到朴素的解决方案，复杂度为O(q*n^2)。

Answer 1

假设您像 m69 的评论中那样沿行求和以生成一个矩阵，其中每个元素都是原始矩阵中相应元素及其左侧所有元素的总和。然后，您执行相同的操作，对该求和矩阵的列求和，得到一个矩阵，其中每个元素都是其左侧和上方元素的矩形子数组的总和。

现在在这个总和数组中取四点:

A B

CD

值 D - B - C + A 包含一个矩形区域的总和，该区域的一个角位于 D，其他角仅位于 A、B 和 C 的 D 侧，您可以通过计算多少次看到添加和减去各个区域中的点。所以在 O(n^2) 的预处理之后你可以在 O(1) 的时间内回答查询