Prefix Sum

AlgorithmsCodingDataStructures Given an array of numbers, arr, the prefix sum or cumulative sum is the sum of all prefixes in arr, i.e. elements in arr up to index :

prefix_sum = [sum(arr[:i+1]) for i in range(n)]

Computational Complexity:

Time Complexity: O(n)
Space Complexity: O(n)
Access: O(1)

Any subarray sum can be computed in time, by computing differences between two elements in the prefix_sum. Therefore this data structure is most applicable for querying some function of values within a range of a fixed array; this can be generalized to other functions f(x) than the sum:

prefix_sum = [f(arr[:i+1]) for i in range(n)]

For infinite sequences, prefix sums are just the partial sums of the sequence’s series. Partial summing is a linear operator on the vector space of sequences whose inverse operator is the finite difference.

The prefix sum can be generalized to arrays and are called integral images in image processing and can be used to efficiently compute the variance of an image patch, useful for efficient image convolution.