Prefix Sum
An interactive, step-by-step visualisation of Prefix Sum.
- Category
- Algorithmic Techniques
- Time complexity
- O(n) build, O(1) query
- Space complexity
- O(n)
Pseudocode
prefix[0] = 0 prefix[i+1] = prefix[i] + a[i] rangeSum(l, r) = prefix[r+1] − prefix[l]
Reference implementation
prefix = [0]
for v in a: prefix.append(prefix[-1] + v)
def range_sum(l, r): return prefix[r+1] - prefix[l]