二次元区間和

今回は paiza の「二次元区間和」の問題に挑戦！

前回の「二次元累積和」と前々回の「区間和」の応用で解ける！

問題概要

📥【入力】

• 最初の行に H W N（整数）
  • H：行数（1 ≦ H ≦ 1000）
  • W：列数（1 ≦ W ≦ 1000）
  • N：クエリ数（1 ≦ N ≦ 100000）
• 次に H 行、各行に W 個の整数で構成された行列 A
• 最後に N 行、各行にクエリ：a b c d（1-indexed）
  • クエリは左上 (a,b) から右下 (c,d) までの区間和を求める指定

📤【出力】

各クエリごとに、指定された長方形領域内の要素の合計を 1 行ずつ出力

入力例1

3 3 2
1 2 3
4 5 6
7 8 9
1 1 3 3
1 2 2 3

出力例1

45
16

🔺75点コード：タイムオーバー

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 matrixA = lines.slice(1, H+1).map(line => line.split(' ').map(Number));
    const queries = lines.slice(H+1);
    
    function prefixSum (a, b, c, d) {
        let result = 0;
        
        for(let i = a-1; i < c; i++){
            for(let j = b-1; j < d; j++){
                result += matrixA[i][j];
            }
        }
        
        return result;
    }
    
    for(const q of queries){
        const [a, b, c, d] = q.split(' ').map(Number);
        console.log(prefixSum(a, b, c, d));
    }
});

動作は正しいけど、時間がかかってしまって減点！

✅ 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 matrixA = lines.slice(1, H+1).map(line => line.split(' ').map(Number));
    const queries = lines.slice(H+1);
    
    
    const prefixSum = Array.from({ length : H+1 }, () => Array(W+1).fill(0));
    
    for(let y = 1; y <= H; y++){
        for(let x = 1; x <= W; x++){
            prefixSum[y][x] = matrixA[y-1][x-1]
                            + prefixSum[y-1][x]
                            + prefixSum[y][x-1]
                            - prefixSum[y-1][x-1];
        }
    }
    
    for(const q of queries){
        const [a, b, c, d] = q.split(' ').map(Number);
        const result = prefixSum[c][d]
                     - prefixSum[a-1][d]
                     - prefixSum[c][b-1]
                     + prefixSum[a-1][b-1];
        console.log(result);
    }
});

右下のクエリの範囲の終点地点までの累積値から、

上と左のクエリの範囲外の部分を引き、

重複して引いた左上の部分を足して区間和を求める。

二次元累積和については、前回の記事で詳しく。

✏️まとめ

区間和は、クエリの区間の終わりまでの累積和から、クエリの区間より前の累積和（クエリに含まれない区間）を引いて求める。

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

未来の自分へ
直近二日前までの自分の記事を参考にして解いたよ(^^)
もし復習することがあれば、そちらも合わせて見てね！