Prefix Sum Of 3D Array

Prerequisite: Prefix Sum – 1D, Prefix Sum -2D

Given a 3-Dimensional array of integers A[L][R][C], where L, R, and C are dimensions of the array (Layer, Row, Column). Find the prefix sum 3d array for it. Let the Prefix sum 3d array be pre[L][R][C]. Here pre[k][i][j]  gives the sum of all integers between pre[0][0][0] and pre[k][i][j] (including both).

Example:

Input: 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}}

    }

Output: pre[L][R][C] 

Layer 1:

1 2 3 4 

2 4 6 8 

3 6 9 12 

4 8 12 16 

Layer 2:

2 4 6 8 

4 8 12 16 

6 12 18 24 

8 16 24 32 

Layer 3:

3 6 9 12 

6 12 18 24 

9 18 27 36 

12 24 36 48 

Layer 4:

4 8 12 16 

8 16 24 32 

12 24 36 48 

16 32 48 64 

Approach: Consider the above image to understand that the cell  pre[0][0][0] is at the origin of x, y, z-axis. To fill the pre[][][] Array perform the steps below for calculating the prefix sum.

• The element at (0, 0, 0) is directly filled. pre[0][0][0] = A[0][0][0]
• Fill cells of three edges (parallel to x, y, z-axis and made up of cells) using a prefix sum on the one-dimensional array. These edges have common elements pre[0][0][0]
• Iterate in a for loop [1, L] to calculate the prefix sum for one of the axis. pre[i][0][0] = pre[i – 1][0][0] + A[i][0][0];
• Similarly, iterate in the ranges [1. R] and [1, C] to calculate the prefix sums for the other two axes.
• Fill cells of three sides (parallel to xy, yz, zx-plane and made up of cells) using a prefix sum on the two-dimensional array. These sides have common elements pre[0][0][0].
• Iterate in a for loop [1, L] to calculate the prefix sum for the two-dimensional array.
  • Iterate in a for loop [1, R] to calculate the prefix sum for the two-dimensional array.
    • Do the following operation. pre[k][i][0] = A[k][i][0] + pre[k – 1][i][0] + pre[k][i – 1][0]  – pre[k – 1][i – 1][0]
• Similarly, calculate for the other 2 sides or prefix sums for the other two-dimensional arrays.
• Iterate in a for loop [1, L] to calculate the prefix sum for three-dimensional array pre[][][].
  • Iterate in a for loop [1, R] to calculate the prefix sum for three-dimensional array pre[][][].
    • Iterate in a for loop [1, C] to calculate the prefix sum for three-dimensional array pre[][][].
      • Do the following operation. 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]
• Finally, print the three-dimensional array pre[][][].

Below is the implementation of the above approach.

Layer 1:
1 2 3 4 
2 4 6 8 
3 6 9 12 
4 8 12 16 

Layer 2:
2 4 6 8 
4 8 12 16 
6 12 18 24 
8 16 24 32 

Layer 3:
3 6 9 12 
6 12 18 24 
9 18 27 36 
12 24 36 48 

Layer 4:
4 8 12 16 
8 16 24 32 
12 24 36 48 
16 32 48 64 

Time Complexity: O(L*R*C)  
Auxiliary Space: O(L*R*C)