三维前缀和
cpp
// 计算三维前缀和
void computePrefixSum(vector<vector<vector<int>>>& A, vector<vector<vector<int>>>& S, int n, int m, int p) {
// 初始化前缀和数组 S
S.resize(n + 1, vector<vector<int>>(m + 1, vector<int>(p + 1, 0)));
// 计算前缀和
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = 1; k <= p; ++k) {
S[i][j][k] = A[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];
}
}
}
}
// 查询指定范围内的子立方体和
int querySum(vector<vector<vector<int>>>& S, int x1, int y1, int z1, int x2, int y2, int z2) {
return S[x2][y2][z2] - S[x1 - 1][y2][z2] - S[x2][y1 - 1][z2] - S[x2][y2][z1 - 1]
+ S[x1 - 1][y1 - 1][z2] + S[x1 - 1][y2][z1 - 1] + S[x2][y1 - 1][z1 - 1]
- S[x1 - 1][y1 - 1][z1 - 1];
}