サイズが M x N の行列の場合、部分行列の合計を見つけるために多数のクエリが必要になります。クエリへの入力は、合計を求める部分行列の左上と右下のインデックスです。 

部分行列の合計クエリを O(1) 時間で実行できるように行列を前処理する方法。 

例：

  tli :   Row number of top left of query submatrix   tlj :   Column number of top left of query submatrix   rbi :   Row number of bottom right of query submatrix   rbj :   Column number of bottom right of query submatrix Input: mat[M][N] = {{1 2 3 4 6} {5 3 8 1 2} {4 6 7 5 5} {2 4 8 9 4} }; Query1: tli = 0 tlj = 0 rbi = 1 rbj = 1 Query2: tli = 2 tlj = 2 rbi = 3 rbj = 4 Query3: tli = 1 tlj = 2 rbi = 3 rbj = 3; Output: Query1: 11 // Sum between (0 0) and (1 1) Query2: 38 // Sum between (2 2) and (3 4) Query3: 38 // Sum between (1 2) and (3 3)

単純なアルゴリズム:  

すべてのクエリをループし、O (q*(N*M)) の最悪のケースで各クエリを計算できますが、これは大きな範囲の数値には大きすぎます。

// Pseudo code of Naive algorithm. Arr[][] = input_matrix For each query: Input tli tlj rbi rbj sum = 0 for i from tli to tbi (inclusive): for j from tlj to rbj(inclusive): sum += Arr[i][j] print(sum) 

最適化されたソリューション: 

合計面積テーブル このタイプのクエリの前処理時間は O(M*N) に短縮され、各クエリは O(1) で実行されます。 Summed Area Table は、グリッドの長方形のサブセット内の値の合計を迅速かつ効率的に生成するためのデータ構造およびアルゴリズムです。 

合計面積テーブルの任意の点 (x y) の値は、(x y) の上下を含むすべての値の合計です。

最適化されたソリューションは以下の投稿で実装されています。

  最適化されたアプローチの実装