Mastery Points
0
Prefix Sum Technique in dsa
Context & Logic
Prefix sum is a preprocessing technique where an array is created such that each element at index 'i' stores the sum of all elements from index 0 to 'i'. This allows O(1) range sum queries.
Example
const arr = [1, 2, 3, 4];
const prefix = [1, 3, 6, 10]; // Precomputed
// Sum of range [1, 2] = prefix[2] - prefix[0] = 6 - 1 = 5Step-by-Step Logic
1
Initialize a prefix array of the same size.
2
Set prefix[0] = arr[0].
3
For i from 1 to n-1: prefix[i] = prefix[i-1] + arr[i].
4
To get sum(L, R): if L == 0 return prefix[R] else return prefix[R] - prefix[L-1].
Complexity Metrics
Time Efficiency
Precomputation: O(n), Query: O(1)
Memory Footprint
O(n) for prefix array