需要數據結構來支持矩陣操作

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)。