この問題はいわゆる累積和 の練習問題です。 数列に対する累積和( \(1\) 次元累積和) を知っていることを前提とします。

\(1\) 次元累積和は以下のような問題を解くときに用います。

長さ \(N\) の数列 \(A\) が与えられます。 以下の \(Q\) 個のクエリを処理してください。

\(i\) 番目のクエリでは \(1 \leq L_i \leq R_i \leq N\) を満たす整数の組 \((L_i,R_i)\) が与えられるので、\(\sum_{k=L_i}^{R_i}A_k\) を求めてください

この問題の解法として、長さ \(N+1\) の数列 \(S=(S_0,S_1,\ldots S_N)\) を \(S_0=0,S_i=\sum_{k=1}^{i-1}A_k\) と定義し 、\(\sum_{k=L_i}^{R_i}A_k=S_{R_i+1}-S_{L_i}\) を利用して各クエリを高速に求めるという解法があります。

この解法における \(S\) を一般的に \(A\) の累積和と呼んだりすることがあります。

今回の問題はこの \(1\) 次元累積和の問題を \(3\) 次元に拡張したものになっています。

先ほどの定義と似たように \(1 \leq i,j,k \leq N+1\) に対して\(S_{i,j,k}=\sum_{x=1}^{i-1} \sum_{y=1}^{j-1}\sum_{z=1}^{k-1}A_{x,y,z}\) を満たす\(S\) を考えます。(\(i,j,k\) のいずれかが \(0\) のとき、\(S_{i,j,k}=0\) とします。)

このとき、\(\sum_{x=Lx_i}^{Rx_i} \sum_{y=Ly_i}^{Ry_i} \sum_{z=Lz_i}^{Rz_i} A_{x,y,z}=S_{Rx_i+1,Ry_i+1,Rz_i+1}-S_{Lx_i,Rx_i+1,Rz_i+1}-S_{Rx_i+1,Ly_i,Rz_i+1}-S_{Rx_i+1,Ry_i+1,Lz_i}+S_{Lx_i,Ly_i,Rz_i+1}+S_{Lx_i,Ry_i+1,Lz_i}+S_{Rx_i+1,Ly_i,Lz_i}-S_{Lx_i,Ly_i,Lz_i}\) を満たします。

そのため、\(S\) を高速に求めることができれば、各クエリを定数時間で処理することができます。

実際に、\(S\) を高速に求める際は、\(S_{i,j,k}=S_{i-1,j,k}+S_{i,j-1,k}+S_{i,j,k-1}-S_{i-1,j-1,k}-S_{i-1,j,k-1}-S_{i,j-1,k-1}+S_{i-1,j-1,k-1}+A_{i-1,j-1,k-1}\) を満たすことを利用することで求められます。時間計算量は\(O(N^3+Q)\) になります。

詳細は実装例を参照してください。

実装例(C++):

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

int main() {
    int n;
    cin >> n;
    vector a(n, vector(n, vector(n, 0)));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                cin >> a[i][j][k];
            }
        }
    }
    vector sum(n + 1, vector(n + 1, vector(n + 1, 0LL)));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                sum[i + 1][j + 1][k + 1] =
                    sum[i][j + 1][k + 1] + sum[i + 1][j][k + 1] +
                    sum[i + 1][j + 1][k] - sum[i][j][k + 1] - sum[i][j + 1][k] -
                    sum[i + 1][j][k] + sum[i][j][k] + a[i][j][k];
            }
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int lx, rx, ly, ry, lz, rz;
        cin >> lx >> rx >> ly >> ry >> lz >> rz;
        lx--, ly--, lz--;
        cout << sum[rx][ry][rz] - sum[lx][ry][rz] - sum[rx][ly][rz] -
                    sum[rx][ry][lz] + sum[lx][ly][rz] + sum[lx][ry][lz] +
                    sum[rx][ly][lz] - sum[lx][ly][lz]
             << "\n";
    }
}

実装例(Python):

n = int(input())

a = [[[0] * n for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        a[i][j]=list(map(int,input().split()))

sum = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]

for i in range(n):
    for j in range(n):
        for k in range(n):
            sum[i + 1][j + 1][k + 1] = (sum[i][j+1][k+1]
                                        + sum[i+1][j][k+1]
                                        + sum[i+1][j+1][k]
                                        - sum[i][j][k+1]
                                        - sum[i][j+1][k]
                                        - sum[i+1][j][k]
                                        + sum[i][j][k]
                                        + a[i][j][k])

q = int(input())
for _ in range(q):
    lx, rx, ly, ry, lz, rz = map(int, input().split())
    lx -= 1
    ly -= 1
    lz -= 1

    result = (sum[rx][ry][rz]
                - sum[lx][ry][rz]
                - sum[rx][ly][rz]
                - sum[rx][ry][lz]
                + sum[lx][ly][rz]
                + sum[lx][ry][lz]
                + sum[rx][ly][lz]
                - sum[lx][ly][lz])
    print(result)