二次元累積和

Posted at 2025-07-31

今回はpzizaのクエリで「二次元累積和」の問題に挑戦！

前回の「区間和」の問題を解いたときの学びを活かして解くことができた！

問題概要

与えられるもの

行数 H、列数 W の行列 A（サイズは H 行 W 列）
累積和を求めたいセルの座標ペアが N 個

求めるもの

各ペア (y, x) について、行列 A の左上 (1,1) から指定された位置 (y, x) までの部分和（累積和）を求める

累積和 S(y, x) の定義

S(y, x) は (1,1) から (y,x) までの矩形領域に含まれるすべての要素の合計

入力例1

3 3 3 // H W N
1 2 3
4 5 6
7 8 9
1 1
2 2
3 3

出力例1

1
12
45

🔺NG例：タイムオーバー

const rl = require('readline').createInterface({input:process.stdin});
const lines = [];
rl.on('line', (input) => lines.push(input));


rl.on('close', () => {
    const [H, W, N] = lines[0].split(' ').map(Number);
    const matrix = lines.slice(1, H+1).map(line => line.split(' ').map(Number));
    
    function prefixSum (y, x){
        let result = 0
        for(let i = 0; i < y; i++){
            for(let j = 0; j < x; j++){
                result +=  matrix[i][j];
            }
        }
        return result;
    }
    
    const query = lines.slice(H+1);
    for(const q of query){
        const [y, x] = q.split(' ').map(Number);
        console.log(prefixSum(y, x));
    }
});

❌ 問題点：

クエリが来るたびに、(0,0)〜(y-1,x-1)を毎回ループして計算。
各クエリが O(H×W)、クエリが N 個あれば O(NHW) → 重すぎてタイムアウト！

✅ OK例：

const rl = require('readline').createInterface({input:process.stdin});
const lines = [];
rl.on('line', (input) => lines.push(input));


rl.on('close', () => {
    const [H, W, N] = lines[0].split(' ').map(Number);
    const matrix = lines.slice(1, H+1).map(line => line.split(' ').map(Number));
    
    const prefixSum = [];
    for(let i = 0; i < H; i++){
        // 各行の 0 番目を 0 で設定
        const temp = [0];
        for(let j = 0; j < W; j++){
            temp[j+1] = temp[j] + matrix[i][j];  
        }
        
        prefixSum.push(temp);
    }
    
    const query = lines.slice(H+1);
    for(const q of query){
        const [y, x] = q.split(' ').map(Number);
        
        let result = 0;
        for(let i = 0; i < y; i++){
            result += prefixSum[i][x];
        }
        
        console.log(result);
    }
});

各行ごとに、左からの和を1行分だけあらかじめ計算（前処理）
→ 1行あたりの 0 番目から x 番目までの和

各行の「横合計」が prefixSum[i][x] で即わかる

それを y 行ぶん足し合わせるだけ

各クエリ O(H)、もとの O(H×W) から高速化！

✨ OK例：二次元累積和

const rl = require('readline').createInterface({input: process.stdin});
const lines = [];

rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [H, W, N] = lines[0].split(' ').map(Number);
    const A = lines.slice(1, H+1).map(row => row.split(' ').map(Number));
    const queries = lines.slice(H+1).map(line => line.split(' ').map(Number));

    // 累積和テーブルを 1-indexed で用意
    const S = Array.from({ length: H + 1 }, () => Array(W + 1).fill(0));

    // 2D prefix sum 作成
    for (let y = 1; y <= H; y++) {
        for (let x = 1; x <= W; x++) {
            S[y][x] = A[y - 1][x - 1]
                    + S[y - 1][x]
                    + S[y][x - 1]
                    - S[y - 1][x - 1];
        }
    }

    // クエリ処理（O(1)）
    for (const [y, x] of queries) {
        console.log(S[y][x]);
    }
});

S[y][x] は左上 (1,1) 〜 (y,x) の範囲の合計
クエリごとに O(1) で即答可能！
前処理だけ O(HW)、その後のクエリは超高速

🔍 累積和テーブルの初期化（1-indexed）

const S = Array.from({ length: H + 1 }, () => Array(W + 1).fill(0));

S は縦 (H+1) 行 × 横 (W+1) 列の 2次元配列を作っていて、

実際にデータを入れるのは S[1][1] 〜 S[H][W]
S[0][*] や S[*][0] は番兵（ダミー行列）として 0 で埋めておく

元の配列 A は 0-indexed だけど、累積和テーブルは 1-indexed にすることで、境界条件の処理がシンプルになるから！

🔍 2次元累積和 S[y][x] を求める時の構造

これは「左上 (1,1) から、現在位置 (y,x) までの "長方形の範囲全体" の合計」を求めるもの。

S[y][x] = A[y-1][x-1]  // 現在の値を加える
        + S[y-1][x]    // 上から来た累積和を加える
        + S[y][x-1]    // 左から来た累積和を加える
        - S[y-1][x-1]; // 左上（重複）を1回引く

+------------------+-------------+  ----
|   重複A       　  |↑上からの合計  |
|   S[y-1][x-1]    |S[y-1][x]|   |  ←上の長方形
+------------------+-------------+  ----
| ← 左からの合計     | 現在地       |
|   S[y][x-1]      | A[y-1][x-1] |
+------------------+-------------+

|    ↑左の長方形  　 |

現在値＋上の長方形＋左の長方形ー重なった長方形

✅ 例:

もし 3×3 行列がこうだとする：

1 2 3
4 5 6
7 8 9

これで S[2][2] を求めたいとすると(y=2, x=2)…

A[1][1] = 5（現在地）
S[1][2] = 1 + 2 = 3（上から）
S[2][1] = 1 + 4 = 5（左から）
S[1][1] = 1（重複）

なので：

S[2][2] = 5 + 3 + 5 – 1 = 12

左上(1,1) ~ y=2,x=2 (2,2) の範囲

|1|2| 上(行)
|4|5|
 左
(列)

現在 5
上　 1, 2
左 　1, 4
重複 1

🗒️ メモ

複数回のクエリに備える場合は「前処理」が鍵
→ O(1) で答えるために、最初に O(H×W) で累積和を作る。

累積和を使えば、「ある範囲の和」を一瞬で求められる。
→ 一度しか使わないなら不要。でも「何度も聞かれる」なら超強力。

2次元にも1次元の発想はそのまま通用する！
→ 区間の和 = 終点までの和 – 始点より前の和 の考えを2Dにも応用できる。

1-indexed の累積和配列を使うとバグが減る！
→ 0行0列目を番兵にして、境界チェックの if 文をなくせる。

重複して足してしまう部分（左上）を引く！
→ 現在地 +上 +左 −左上

元の配列が0-indexedでも、累積和配列は1-indexedでOK。
→ A[y-1][x-1]

僕の失敗談(´;ω;｀)と解決法🐈

💡おまけ　Array と Array.from

Array.from({ length: H }, () => Array(W).fill(0));

これは：

H 個の要素の配列を作って（≒行数）
各要素に対して Array(W).fill(0) を実行する（≒列数分の 0 を詰めた配列）

つまり、「H 行 W 列」の2次元配列を初期化している。
Array.from は「行数分の要素（= 各行）」を作るために使った。

✅ Array(n) + .fill(0) の関係

Array(W).fill(0)