2次元累積和（Cumulative Sum）は、2次元配列（マトリックス）の部分領域の合計値を効率よく計算するためのデータ構造です。事前に計算しておいた累積和を使うことで、任意の長方形領域の合計値を 定数時間 (O(1)) で求めることができます。

与えられたマス目（グリッド）において、左上 (1, 1) から任意のセル (i, j) までの矩形領域の総和を累積和として保存します。

累積和テーブルを S[i][j] とした場合、以下の式で定義されます： [ S[i][j] = \text{grid}[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1] ]

累積和を使うと、ある長方形領域 (A, B) ～ (C, D) の総和は以下の式で求められます： [ \text{Sum}(A, B, C, D) = S[C][D] - S[A-1][D] - S[C][B-1] + S[A-1][B-1] ]

1. 累積和テーブルの構築

   • (S[i][j]) を上記の式に基づいて計算します。

2. クエリ処理

   • 指定された領域の合計値を累積和テーブルから計算します。

次のようなグリッドがあるとします：

1 2 3
4 5 6
7 8 9

クエリ：(1, 1) ～ (2, 2) の合計値を求める。

まず、累積和テーブル (S) を構築します：

1. (S[1][1] = \text{grid}[1][1] = 1)
2. (S[1][2] = \text{grid}[1][2] + S[1][1] = 2 + 1 = 3)
3. (S[2][1] = \text{grid}[2][1] + S[1][1] = 4 + 1 = 5)
4. その他のセルも同様に計算します。

結果の累積和テーブル：

1   3   6
5  12  21
12 27  45

(1, 1) ～ (2, 2) の領域の合計値を求めます： [ \text{Sum}(1, 1, 2, 2) = S[2][2] - S[0][2] - S[2][0] + S[0][0] ] ここで：

• (S[2][2] = 12)
• (S[0][2] = 0)（範囲外は0とみなす）
• (S[2][0] = 0)（範囲外は0とみなす）
• (S[0][0] = 0)

よって： [ \text{Sum}(1, 1, 2, 2) = 12 - 0 - 0 + 0 = 12 ]

以下は、JavaScriptで2次元累積和を計算し、クエリを処理する例です：

function compute2DCumulativeSum(grid) {
    const H = grid.length;
    const W = grid[0].length;

    // 累積和テーブルの準備
    const S = Array.from({ length: H + 1 }, () => Array(W + 1).fill(0));

    // 累積和の計算
    for (let i = 1; i <= H; i++) {
        for (let j = 1; j <= W; j++) {
            S[i][j] = grid[i - 1][j - 1] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
        }
    }

    return S;
}

function querySum(S, A, B, C, D) {
    return S[C][D] - S[A - 1][D] - S[C][B - 1] + S[A - 1][B - 1];
}

// 入力グリッド
const grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
];

// 累積和の構築
const S = compute2DCumulativeSum(grid);

// クエリ例：(1, 1) ～ (2, 2)
const result = querySum(S, 1, 1, 2, 2);
console.log(result); // 12

1. 前処理 (O(H \times W)): 累積和テーブルの構築には (H \times W) の計算が必要。

2. クエリ処理 (O(1)): 任意のクエリに対して、累積和テーブルを使うことで即座に結果を取得可能。

3. 使える条件:

   • 部分和を効率よく計算したい場合。
   • グリッドの値が頻繁に変化しない場合（更新操作には適していない）。

• 画像処理（濃度や輝度の部分合計）。
• 領域計算やヒートマップ分析。
• データサイエンスやゲームなどの効率的な範囲計算。