鉄則本 A08 - Two Dimensional Sum (2Q, ★4)

二次元累積和！

• 問題へのリンク

問題概要

のグリッドがあり、マス には値 が書かれている。次の 個のクエリに答えよ。

【クエリ】
左上が 、右上が であるような長方形領域が与えられるので、領域内のマスに書かれた整数の総和を求めよ。

制約

• 

解法

鉄則本に載っている問題なので、鉄則本を参照。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int H, W, Q;
    cin >> H >> W;
    vector X(H, vector(W, 0));
    for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) cin >> X[i][j];
    
    // 二次元累積和を求める
    vector S(H + 1, vector(W + 1, 0));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            S[i + 1][j + 1] = S[i + 1][j] + X[i][j];
        }
    }
    for (int j = 0; j < W + 1; ++j) {
        for (int i = 0; i < H; ++i) {
            S[i + 1][j] += S[i][j];
        }
    }

    // クエリ
    cin >> Q;
    while (Q--) {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        --A, --B;
        
        int res = S[C][D] - S[A][D] - S[C][B] + S[A][B];
        cout << res << endl;
    }
}