三维前缀和

模板题D - Cuboid Sum Query

求和

sum[i][j][k]=a[i][j][k]+sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]-sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j-1][k-1]+sum[i-1][j-1][k-1];

查询

ans = sum[x2][y2][z2]-sum[x1-1][y2][z2]-sum[x2][y1-1][z2]-sum[x2][y2][z1-1]+sum[x1-1][y1-1][z2]+sum[x1-1][y2][z1-1]+sum[x2][y1-1][z1-1]-sum[x1-1][y1-1][z1-1]

完整代码

/*
* @Author:  Hfuubigstrength
* @email:   2854614012@qq.com
* @Date:   2024-08-19 19:48:29
*/
#include <bits/stdc++.h>
//#define int long long
#define PII pair<int,int>
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
#define r(x, y) rand() % (y - x + 1) + x
using namespace std;

const int N = 110;
int a[N][N][N], sum[N][N][N], n, m;

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            for(int k = 1; k <= n; k ++ )
                cin >> a[i][j][k];
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            for(int k = 1; k <= n; k ++ )
                sum[i][j][k]=a[i][j][k]+sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]-sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j-1][k-1]+sum[i-1][j-1][k-1];
    cin >> m;
    while(m -- ){
        int x1, x2, y1, y2, z1, z2; cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
        cout << sum[x2][y2][z2]-sum[x1-1][y2][z2]-sum[x2][y1-1][z2]-sum[x2][y2][z1-1]+sum[x1-1][y1-1][z2]+sum[x1-1][y2][z1-1]+sum[x2][y1-1][z1-1]-sum[x1-1][y1-1][z1-1] << endl;
    }
    return 0;
}