Prefix Sum Visualization & Animation

Preprocesses cumulative sums so any range sum query can be answered in O(1) after O(n) build time.

## What is it? Prefix Sum (also called cumulative sum) preprocesses an array so that any range sum query `sum(i, j)` can be answered in O(1) time. Instead of summing every time, you precompute running totals. ## How it works **Build:** - `prefix[0] = 0` - `prefix[i] = prefix[i-1] + arr[i-1]` for i from 1 to n **Query (sum from index l to r inclusive):** - `sum(l, r) = prefix[r+1] - prefix[l]` ## When to use - Multiple range sum queries on a static array - Subarray sum problems (combined with a hash map for the "sum equals k" pattern) - 2D prefix sums for matrix range queries - Difference arrays for range update + point query ## Key Points - O(n) build, O(1) query — ideal when queries vastly outnumber updates - Zero-indexed prefix array of size n+1 eliminates off-by-one errors - For "subarray sum equals k": use a HashMap storing prefix sum frequencies

Category: algorithms

Difficulty: beginner

Time Complexity: O(n) build, O(1) query

Space Complexity: O(n)

Prefix Sum

beginner

Preprocesses cumulative sums so any range sum query can be answered in O(1) after O(n) build time.

GFGLeetCode
3
[0]
1
[1]
4
[2]
1
[3]
5
[4]
9
[5]
prefix[i] = prefix[i-1] + arr[i]
Prefix Sum Array
[0]
[1]
[2]
[3]
[4]
[5]

Starting prefix sum build. Each prefix[i] stores the sum of arr[0..i].

arr[i] being examined
prefix[i-1] referenced
prefix[i] just computed
prefix already filled
Starting prefix sum build. Each prefix[i] stores the sum of arr[0..i].