prerequisite: Prefix Sum – 3D
Given a 3-Dimensional array of integers A[L][R][C]. where L, R, and C are dimensions of the array (Layer, Row, Column). there are large number of queries to find the sum of integers between given cells inclusively. (find the sum of sub 3d array of the given array).
similar articles for 2d array matrix: Submatrix Sum Queries
The total number of Queries is Q. Each query consist of 6 integers k1,i1,j1,k2,i2,j2 indexes of array, and you have to answer sum of integers between A[k1][i1][j1] and A[k2][i2][j2] inclusively.
Example:
Input:
array:
int A[L][R][C] = { {{1, 1, 1, 1}, // Layer 1 {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}},
{{1, 1, 1, 1}, // Layer 2 {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}},
{{1, 1, 1, 1}, // Layer 3 {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}},
{{1, 1, 1, 1}, // Layer 4 {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}}};
Queries:
query = { {0, 0, 0, 1, 1, 1}, {1, 1, 1, 3, 3, 3}, {0, 1, 1, 3, 3, 3}, {0, 0, 0, 3, 3, 3} };
All Query is in form of k1,i1,j1,k2,i2,j2.
here 4 query are given.
Output:
Query 1 : 8Query 2 : 27Query 3 : 36Query 4 : 64
Approach:
- First of all, calculate the prefix sum of given array A[L][R][C].
- and then collect indexes of two given cells from the query array.
- store prefix sum up to A[k2][i2][j2].
// store prefix sum up to A[k2][i2][j2]:int sum = pre[k2][i2][j2];
- apply following operations using if conditions to remove unnecessary cells and remove overlapping.
// unnecessary cells and overlaping removal steps// using if conditions :if (j1 > 0){ sum -= pre[k2][i2][j1 - 1];}if (k1 > 0){ sum -= pre[k1 - 1][i2][j2];}if (i1 > 0){ sum -= pre[k2][i1 - 1][j2];}
if (k1 > 0 && i1 > 0){ sum += pre[0][0][j2];}if (i1 > 0 && j1 > 0){ sum += pre[k2][0][0];}if (j1 > 0 && k1 > 0){ sum += pre[0][i2][0];}
if (k1 > 0 && i1 > 0 && j1 > 0){ sum -= pre[k1 - 1][i1 - 1][j1 - 1];}Implementation:
All calculation of prefix sum is taken from prefix sum of 3d array.
C++ Implementation:
// C++ program for the above approach.#include <bits/stdc++.h>using namespace std;
// Declaring size of the array#define L 4 // Layer#define R 4 // Row#define C 4 // Column
// Calculating prefix sum arrayvoid prefixSum3d(int A[L][R][C], int pre[L][R][C]){ // Step 0: pre[0][0][0] = A[0][0][0];
// Step 1: Filling the first row, // column, and pile of ceils. // Using prefix sum of 1d array for (int i = 1; i < L; i++) pre[i][0][0] = pre[i - 1][0][0] + A[i][0][0];
for (int i = 1; i < R; i++) pre[0][i][0] = pre[0][i - 1][0] + A[0][i][0];
for (int i = 1; i < C; i++) pre[0][0][i] = pre[0][0][i - 1] + A[0][0][i];
// Step 2: Filling the cells // of sides(made up using cells) // which have common element A[0][0][0]. // using prefix sum on 2d array for (int k = 1; k < L; k++) { for (int i = 1; i < R; i++) { pre[k][i][0] = A[k][i][0] + pre[k - 1][i][0] + pre[k][i - 1][0] - pre[k - 1][i - 1][0]; } } for (int i = 1; i < R; i++) { for (int j = 1; j < C; j++) { pre[0][i][j] = A[0][i][j] + pre[0][i - 1][j] + pre[0][i][j - 1] - pre[0][i - 1][j - 1]; } } for (int j = 1; j < C; j++) { for (int k = 1; k < L; k++) { pre[k][0][j] = A[k][0][j] + pre[k - 1][0][j] + pre[k][0][j - 1] - pre[k - 1][0][j - 1]; } }
// Step 3: Filling value // in remaining cells using formula for (int k = 1; k < L; k++) { for (int i = 1; i < R; i++) { for (int j = 1; j < C; j++) { pre[k][i][j] = A[k][i][j]
+ pre[k - 1][i][j] + pre[k][i - 1][j] + pre[k][i][j - 1]
- pre[k - 1][i - 1][j] - pre[k][i - 1][j - 1] - pre[k - 1][i][j - 1]
+ pre[k - 1][i - 1][j - 1]; } } } // we don't have to return pre array because // pre array is passed by reference}
// Driver Codeint main(){ // given array: int A[L][R][C] = { {{1, 1, 1, 1}, // Layer 1 {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}},
{{1, 1, 1, 1}, // Layer 2 {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}},
{{1, 1, 1, 1}, // Layer 3 {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}},
{{1, 1, 1, 1}, // Layer 4 {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1}}};
// given queries: vector<vector<int>> query = { {0, 0, 0, 1, 1, 1}, {1, 1, 1, 3, 3, 3}, {0, 1, 1, 3, 3, 3}, {0, 0, 0, 3, 3, 3}}; int Q = query.size();
int pre[L][R][C]; prefixSum3d(A, pre);
for (int i = 0; i < Q; i++) { // collect indexes of two given cells from the query array: int k1 = query[i][0], i1 = query[i][1], j1 = query[i][2]; int k2 = query[i][3], i2 = query[i][4], j2 = query[i][5];
// store prefix sum up to A[k2][i2][j2]: int sum = pre[k2][i2][j2];
// unnecessary cells and overlaping removal steps // using if conditions : if (j1 > 0) { sum -= pre[k2][i2][j1 - 1]; } if (k1 > 0) { sum -= pre[k1 - 1][i2][j2]; } if (i1 > 0) { sum -= pre[k2][i1 - 1][j2]; }
if (k1 > 0 && i1 > 0) { sum += pre[0][0][j2]; } if (i1 > 0 && j1 > 0) { sum += pre[k2][0][0]; } if (j1 > 0 && k1 > 0) { sum += pre[0][i2][0]; }
if (k1 > 0 && i1 > 0 && j1 > 0) { sum -= pre[k1 - 1][i1 - 1][j1 - 1]; } // printing answer: cout << "Query " << i + 1 << " : "; cout << sum << endl; }
return 0;}
Python Implementation:# python program to calculate prefix sum of 3d array# Declaring size of the arrayL = 4 # LayerR = 4 # RowC = 4 # Column
# Calculating prefix
def prefixSum3d(A):
pre = [[[0 for a in range(C)] for b in range(R)] for d in range(L)]
pre[0][0][0] = A[0][0][0]
# Step 1: Filling the first row,column, and pile of ceils. # Using prefix sum of 1d array for i in range(1, L): pre[i][0][0] = pre[i - 1][0][0] + A[i][0][0]
for i in range(1, R): pre[0][i][0] = pre[0][i - 1][0] + A[0][i][0]
for i in range(1, C): pre[0][0][i] = pre[0][0][i - 1] + A[0][0][i]
# Step 2: Filling the cells of sides(made up using cells) # which have common element A[0][0][0]. # using prefix sum on 2d array for k in range(1, L): for i in range(1, R): pre[k][i][0] = (A[k][i][0] + pre[k - 1][i][0] + pre[k][i - 1][0] - pre[k - 1][i - 1][0]) for i in range(1, R): for j in range(1, C): pre[0][i][j] = (A[0][i][j] + pre[0][i - 1][j] + pre[0][i][j - 1] - pre[0][i - 1][j - 1]) for j in range(1, C): for k in range(1, L): pre[k][0][j] = (A[k][0][j] + pre[k - 1][0][j] + pre[k][0][j - 1] - pre[k - 1][0][j - 1])
# Step 3: Filling value in remaining cells using formula for k in range(1, L): for i in range(1, R): for j in range(1, C): pre[k][i][j] = (A[k][i][j]
+ pre[k - 1][i][j] + pre[k][i - 1][j] + pre[k][i][j - 1]
- pre[k - 1][i - 1][j] - pre[k][i - 1][j - 1] - pre[k - 1][i][j - 1]
+ pre[k - 1][i - 1][j - 1])
return pre
# Driver program to test above function# given array:A = [ [[1, 1, 1, 1], # Layer 1 [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]],
[[1, 1, 1, 1], # Layer 2 [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]],
[[1, 1, 1, 1], # Layer 3 [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]],
[[1, 1, 1, 1], # Layer 4 [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]]# given queries:query = [ [0, 0, 0, 1, 1, 1], [1, 1, 1, 3, 3, 3], [0, 1, 1, 3, 3, 3], [0, 0, 0, 3, 3, 3]]Q = len(query)
# calculating prefix sum:pre = prefixSum3d(A)
# calculating answer for each query:for i in range(Q): # collect indexes of two given cells from the query array: k1 = query[i][0] i1 = query[i][1] j1 = query[i][2] k2 = query[i][3] i2 = query[i][4] j2 = query[i][5]
# store prefix sum up to A[k2][i2][j2] sum = pre[k2][i2][j2]
# overlaping removal steps using if conditions : if j1 > 0: sum -= pre[k2][i2][j1-1] if k1 > 0: sum -= pre[k1-1][i2][j2] if i1 > 0: sum -= pre[k2][i1-1][j2]
if k1 > 0 and i1 > 0: sum += pre[0][0][j2] if i1 > 0 and j1 > 0: sum += pre[k2][0][0] if j1 > 0 and k1 > 0: sum += pre[0][i2][0]
if k1 > 0 and i1 > 0 and j1 > 0: sum -= pre[k1-1][i1-1][j1-1]
# printing answer: print("Query", i+1, end=" : ") print(sum)
Complexity:
Prefix sum:
Time Complexity: O(L*R*C)
Auxiliary Space: O(L*R*C)
Query:
Here all Query Answer takes O(1) Time, the total time complexity is O(Q).
and space required is O(Q*6).
Time Complexity: O(Q)
Auxiliary Space: O(Q)
Final Complexity:
Time Complexity: O(L*R*C+Q)
Auxiliary Space: O(L*R*C+Q)
C++ image:
Python image:
Read also:
0 Comments
If you have any doubt let me know.