Сумма префиксов трехмерного массива

Условие: Сумма префикса — 1D, Сумма префикса — 2D

Дан трехмерный массив целых чисел A[L][R][C] , где L, R и C — размеры массива (слой, строка, столбец). Найдите для него массив префикса sum3d. Пусть массив Prefix sum 3d будет pre[L][R][C]. Здесь pre[k][i][j] дает сумму всех целых чисел между pre[0][0][0] и pre[k][i][j] (включая оба).

Пример:

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 

Подход: рассмотрите изображение выше, чтобы понять, что ячейка pre[0][0][0] находится в начале координат осей x, y, z. Чтобы заполнить массив pre[][][] выполните следующие шаги для вычисления суммы префикса.

• Элемент в (0, 0, 0) заполняется напрямую. пре[0][0][0] = А[0][0][0]
• Заполните ячейки трех ребер (параллельных осям x, y, z и состоящих из ячеек), используя сумму аппрефиксов в одномерном массиве. Эти ребра имеют общие элементы pre[0][0][0]
• Повторите цикл for [1, L], чтобы вычислить сумму префиксов для одной из осей. пре[i][0][0] = пре[i – 1][0][0] + A[i][0][0];
• Аналогичным образом выполните итерацию в диапазонах [1. R] и [1, C] для вычисления сумм префиксов для двух других осей.
• Заполните ячейки трех сторон (параллельные xy, yz, zx-плоскости и состоящие из ячеек), используя сумму префиксов в двумерном массиве. Эти стороны имеют общие элементы pre[0][0][0] .
• Повторите цикл for [1, L], чтобы вычислить сумму префиксов для двумерного массива.
  • Повторите цикл for [1, R], чтобы вычислить сумму префиксов для двумерного массива.
    • Проделайте следующую операцию. pre[k][i][0] = A[k][i][0] + pre[k – 1][i][0] + pre[k][i – 1][0] – pre[ к - 1 [я - 1] [0]
• Аналогичным образом рассчитайте для двух других сторон или суммы префиксов для других двумерных массивов.
• Повторите цикл for [1, L], чтобы вычислить сумму префиксов для трехмерного массива pre[][][].
  • Повторите цикл for [1, R], чтобы вычислить сумму префиксов для трехмерного массива pre[][][].
    • Повторите цикл for [1, C] для вычисления суммы префиксов для трехмерного массива pre[][][].
      • Проделайте следующую операцию. 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] + пред[k – 1][i – 1][j – 1]
• Наконец, напечатайте трехмерный массив pre[][][].

Ниже приведена реализация описанного выше подхода.

Временная сложность : O(L*R*C)
Вспомогательное пространство : O(L*R*C)