Алгоритмы и структуры данных

2D префиксная сумма

Допустим, у нас есть большой двумерный массив чисел с количеством строк r и количеством столбцов c. Необходимо вычислить его 2D префиксную сумму. Префиксная сумма в точке (r, c) — это сумма всех элементов от угла (0, 0) до элемента (r, c) включительно. Иными словами, это сумма элементов подматрицы с вершинами в (0, 0), (r, 0), (r, c) и (0, c).
Сможете ли вы эффективно вычислить 2D префиксную сумму для всех позиций в матрице?
+
+
+
+
ㅤ
ㅤ
ㅤ
+
+
+
+
ㅤ
ㅤ
ㅤ
+
+
+
+
ㅤ
ㅤ
ㅤ
+
+
+
+
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
Video preview

Входные данные

В первой строке входных данных указаны два целых числа — количество строк в матрице r и количество столбцов c (1 ≤ r, c ≤ 1000).
В следующих r строках записано по c целых чисел, разделенных пробелами, которые являются элементами матрицы .

Выходные данные

Программа должна вывести r строк, в каждой из которых содержится c чисел, представляющих собой 2D префиксную сумму матрицы.

Примеры

Входные данные
Выходные данные
3 5 1 2 -3 4 6 -1 3 8 4 0 0 1 -2 0 5
1 3 0 4 10 0 5 10 18 24 0 6 9 17 28
 

Constraints

Time limit: 6 seconds

Memory limit: 512 MB

Output limit: 15 MB

To check your solution you need to sign in
Sign in to continue