Prefix Sum

Given an array \(v\), returns a new array where its \(i\)th element is equal to \(v[0] + v[1] + .. + v[i]\). The following algorithm solves the problem with \(O(n)\) time and space complexity where \(n\) is the number of elements in the array.

Useful when the problem requires query and update of the prefix sum.

• Wikipedia
• Tushar Roy's Fenwick Tree explanation

Given a two-dimensional array, returns a new two-dimensional array where each position \((i, j)\) is the sum of all number in the subarray from the position \((0,0)\) to \((i,j)\). The following code solves the problem with \(O(n \times m)\) time and space complexity.

• Matrix