Задача — вычислить префиксную сумму матрицы или двумерного массива с помощью Python. Префиксная сумма матрицы – это новая матрица, каждый элемент которой представляет собой сумму всех элементов подматрицы, образованной верхним левым углом и текущим элементом.

Вот один из способов вычисления префиксной суммы матрицы:

Метод 1: наивный подход

1. Создайте новую матрицу того же размера, что и входная матрица, инициализированную нулями.
2. Пройти по каждой строке и столбцу входной матрицы.
3. Для каждого элемента входной матрицы вычислите сумму всех элементов подматрицы, образованной верхним левым углом и текущим элементом.
4. Обновить соответствующий элемент в новой матрице, указав вычисленную сумму.
5. Вернуть новую матрицу как сумму префикса входной матрицы.

Вот реализация описанного выше метода на Python:

def prefix_sum_matrix(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    # Create a new matrix initialized with zeros
    prefix_sum = [[0] * cols for _ in range(rows)]
    # Compute prefix sum
    for i in range(rows):
        for j in range(cols):
            # Calculate sum of elements in the submatrix
            prefix_sum[i][j] = matrix[i][j]
            if i > 0:
                prefix_sum[i][j] += prefix_sum[i - 1][j]
            if j > 0:
                prefix_sum[i][j] += prefix_sum[i][j - 1]
            if i > 0 and j > 0:
                prefix_sum[i][j] -= prefix_sum[i - 1][j - 1]
    return prefix_sum
# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
result = prefix_sum_matrix(matrix)
print(result)

Это выведет:

[[1, 3, 6],
 [5, 12, 21],
 [12, 27, 45]]