“¿Cómo construir una matriz de suma de prefijo en Python?” Código de respuesta

¿Cómo construir una matriz de suma de prefijo en Python?

"""
How to construct a prefix sum array?
Prefix sum array helps respond to sum queries
on an array efficiently.
[1, 3, 4, 8]: original array --> [1, 4, 8, 16]: prefix sum
Sum query sumq(idx1, idx2) = sumq(0, b) - sumq(0, a-1)
Let n denote the size of the original array.
Time complexity: O(n)
Space complexity: O(n)
"""
def prefix_sum(array):
    pref_sum_arr = [0]
    n = len(array)
    for idx in range(1, n+1):
        pref_sum_arr.append(pref_sum_arr[idx-1] + array[idx-1])
    return pref_sum_arr

arr = [1, 3, 4, 8]
print(prefix_sum(arr)[1:])  # [1, 4, 8, 16]