Gọi ~S_{xyzt}~ là tổng của các ~a_{x'y'z't'}~ với ~1 \leq x' \leq x~; ~ 1 \leq y' \leq y~ ; ~ 1 \leq z' \leq z~ ; ~1 \leq t' \leq t~. Sau đó ~S_{xyzt}~ được tính bằng bao hàm loại trừ như sau:

s[x][y][z][t] = a[x][y][z][t];
for (int mask = 1; mask < 16; mask++) {
    int nx = x - ((mask & 1) > 0);
    int ny = y - ((mask & 2) > 0);
    int nz = z - ((mask & 4) > 0);
    int nt = t - ((mask & 8) > 0);
    if (((nx != x) + (ny != y) + (nz != z) + (nt != t)) % 2)
        s[x][y][z][t] += s[nx][ny][nz][nt];
    else
        s[x][y][z][t] -= s[nx][ny][nz][nt];
}

Ta sẽ tính ~S_{xyzt}~ đựa vào các ~S_{x | x-1, y | y-1, z | z-1, t | t-1}~ thì Bit thứ ~i~ (~0~, ~1~, ~2~ hoặc ~3~) của mask sẽ đại diện cho việc ta lấy ~x~ hay ~x-1~, ~y~ hay ~y-1~, ~\dots~ Theo nguyên lí bù trừ, nếu số Bit là lẻ thì ta cộng ~S~ đó vào ~S_{xyzt}~ ngược lại ta trừ ~S_{xyzt}~ cho ~S~ đó.

Để tính truy vấn, ta cũng sử dụng nguyên lí tương tự, nhưng ta sẽ chọn ~x_2~ nếu Bit thứ ~0~ bằng ~0~ và ~x_{1}-1~ nếu Bit thứ ~0~ bằng ~1~, tương tự với ~y~, ~z~ và ~t~

ll getSum(int x, int y, int z, int t, int xx, int yy, int zz, int tt) {
    ll ans = s[xx][yy][zz][tt];
    for (int mask = 1; mask < 16; mask++) {
        int nx = (mask & 1) > 0 ? x - 1 : xx;
        int ny = (mask & 2) > 0 ? y - 1 : yy;
        int nz = (mask & 4) > 0 ? z - 1 : zz;
        int nt = (mask & 8) > 0 ? t - 1 : tt;
        if (((nx != xx) + (ny != yy) + (nz != zz) + (nt != tt)) % 2)
            ans -= s[nx][ny][nz][nt];
        else
            ans += s[nx][ny][nz][nt];
    }
    return ans;
}

Code mẫu

#include <bits/stdc++.h>
#define TASK ""
#define pb push_back
#define F first
#define S second
#define FOR(i, a, b) for (int i=a; i<=b; i++)
#define FOr(i, a, b) for (int i=a; i<b ; i++)
#define FOD(i, a, b) for (int i=a; i>=b; i--)
#define FOd(i, a, b) for (int i=a; i>b ; i--)
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;

const int N=1e6+7;
const int MOD=1e9+7;
const ll INF=(ll)1e18+7;
int a[41][41][41][41];
ll s[41][41][41][41];
int m, n, p, q;

void prepare() {
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= m; y++)
            for (int z = 1; z <= p; z++)
                for (int t = 1; t <= q; t++) {
                    s[x][y][z][t] = a[x][y][z][t];
                    for (int mask = 1; mask < 16; mask++) {
                        int nx = x - ((mask & 1) > 0);
                        int ny = y - ((mask & 2) > 0);
                        int nz = z - ((mask & 4) > 0);
                        int nt = t - ((mask & 8) > 0);
                        if (((nx != x) + (ny != y) + (nz != z) + (nt != t)) % 2)
                            s[x][y][z][t] += s[nx][ny][nz][nt];
                        else
                            s[x][y][z][t] -= s[nx][ny][nz][nt];
                    }
                    //cout << s[x][y][z][t] << '\n';
                }
}

ll getSum(int x, int y, int z, int t, int xx, int yy, int zz, int tt) {
    ll ans = s[xx][yy][zz][tt];
    for (int mask = 1; mask < 16; mask++) {
        int nx = (mask & 1) > 0 ? x - 1 : xx;
        int ny = (mask & 2) > 0 ? y - 1 : yy;
        int nz = (mask & 4) > 0 ? z - 1 : zz;
        int nt = (mask & 8) > 0 ? t - 1 : tt;
        if (((nx != xx) + (ny != yy) + (nz != zz) + (nt != tt)) % 2)
            ans -= s[nx][ny][nz][nt];
        else
            ans += s[nx][ny][nz][nt];
    }
    return ans;
}

// ll bruforces(int x, int y, int z, int t, int xx, int yy, int zz, int tt) {
//     ll ans = 0;
//     for (int i = x; i <= xx; i++)
//     for (int j = y; j <= yy; j++)
//     for (int k = z; k <= zz; k++)
//     for (int l = t; l <= tt; l++)
//         ans += a[i][j][k][l];
//     return ans;
// }

int main() {
    #ifdef TriPhan
        freopen("TEST.INP","r",stdin);
        freopen("TEST.OUT","w",stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
    #endif
    cin >> n >> m >> p >> q;
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= m; y++)
            for (int z = 1; z <= p; z++)
                for (int t = 1; t <= q; t++)
                    cin >> a[x][y][z][t];

    prepare();
    // for (int x = 1; x <= n; x++)
    // for (int y = 1; y <= m; y++)
    // for (int z = 1; z <= p; z++)
    // for (int t = 1; t <= q; t++)
    // for (int xx = x; xx <= n; xx++)
    // for (int yy = y; yy <= m; yy++)
    // for (int zz = z; zz <= p; zz++)
    // for (int tt = t; tt <= q; tt++)
    //     if ((getSum(x, y, z, t, xx, yy, zz, tt) != bruforces(x, y, z, t, xx, yy, zz, tt))) 
    //         cout << 'a';
    int t;
    cin >> t;
    while (t--) {
        int x1, y1, z1, t1, x2, y2, z2, t2;
        cin >> x1 >> y1 >> z1 >> t1 >> x2 >> y2 >> z2 >> t2;
        cout << getSum(x1, y1, z1, t1, x2, y2, z2, t2) << '\n';
    }
}