An interactive step-by-step visualisation of the Prefix Sum pattern. Watch how precomputing cumulative sums enables O(1) range sum queries after O(n) preprocessing.
1def build_prefix(nums: list[int]) -> list[int]:2 prefix = [0]3 for num in nums:4 prefix.append(prefix[-1] + num)5 return prefix67def range_sum(prefix: list[int], i: int, j: int) -> int:8 return prefix[j + 1] - prefix[i]
We have an array [3, 1, 4, 1, 5, 9] and need to efficiently answer range sum queries like "sum from index 1 to 4".