需要数据结构来支持矩阵操作

Question

我需要一个特定的数据结构，我不知道应该使用什么。

我有一个矩阵NxN。每个单元格都有一些整数值。对于在基质的任何矩形我需要计算一个“价格”，使得：

price = sum(#value_of_field * #distance_from_target) over cells in rectangle 

距离是曼哈顿距离和目标可以是在矩形的任何细胞。矩阵是固定的（不变的）。

实施例：

1 2 
1 2 

左上角为[0; 0]，左底部是[0; 1]，右上为[1 0]和右底部是[1; 1]

例如，给定[0; 0]在矩形[0; 0] - [1; 1]（整个矩阵）的价格将是：

price = 1 * 0  +  2 * 1  + 1 * 1   +  2 * 2 = 7 
     price of   price of   
     [0;0] *   [1;0] *   .....     .... 
     distance   distance 
     from [0;0]   from [0;0] 

我应该如何解决这个问题？在m×n中的解（其中m，n是矩形的维数）很容易，但速度很慢。如何加速（例如预先计算某些东西）？

Answer 1

计算Ai和Bi提前：

• 艾=元素对第i和行
• 的Bi =元素对总和第i列

这会给你答案。

对于每个价格计算，时间复杂度为O(N)。准备Ai和Bi的时间复杂度也是O(N)。