c++ - 编程任务 : sum of submatrices

Question

我在解决我的编程任务时遇到了问题。事实上，我解决了它，但我的代码没有通过一些测试(时间监督)。

任务正文如下:
我们有一个大小为 N*N 的矩阵。输入的第一行包含两个整数:N 和 K。K 是定义子矩阵的行数。
接下来的 N 行包含主矩阵的元素(空格作为元素的分隔符，\n 作为行的分隔符)。之后我们有 K 行定义子矩阵。

定义如下:
y_l x_l y_r x_r 其中(x_l, y_l)是主矩阵中子矩阵左上角的列和行，(x_r, y_r)是子矩阵右下角的列和行。我们必须计算所有子矩阵的总和并将其划分为等价类(如果总和相等，则子矩阵属于一个类)。

程序的输出应该如下:
三个整数(除以空格)，其中第一个是等价类的数量，第二个是具有最大元素的等价类的数量，第三个是所有子矩阵总和的平均值。

从测试中我发现问题出在总和的计算上:

while(true){
    for(int i = x_l; i <= x_r; i++)
        sum += *diff++;
    if(diff == d_end) break;
    d_start = d_start + size;
    diff = d_start;
}

但我不知道如何优化它。可能有人可以给我算法或一些想法如何更快地计算这些总和。谢谢。

更新:回答
经过几天的搜索，我终于得到了我的程序的工作版本。感谢 Yakk，它给了一些非常有用的建议。
最后是 code.
非常有用的链接，奇怪的是我以前找不到，除非我问一个非常具体的问题(基于 Yakk 给我的信息)link.
我希望我的代码将来可能对某人有所帮助。

Answer 1

建立求和矩阵。

求和矩阵中的位置(a,b)处，将原矩阵中(a,b)的左&上(包括(a,b)处)所有元素求和。

现在计算子矩阵的和是 4 次查找，一次加法和两次减法。绘制一个 4x4 矩阵并使用这样的和来表示右下角的 2x2，看看如何实现。

如果将存储的数据加倍，则可以将查找减半。但我不会打扰。

如果您仔细操作，构建求和矩阵只需要少量工作。