Prefix Sum Visualization
Precompute sums to answer range sum queries in O(1) time.
Original Array (arr)
Prefix Sum Array (P)
L:
R:
Ready to start
Ready
Speed
Pseudocode
1function buildPrefixSum(arr)
2 P[0] = arr[0]
3 for i = 1 to n-1
4 P[i] = P[i-1] + arr[i]
5
6 // Range Query(L, R)
7 if L == 0: return P[R]
8 return P[R] - P[L-1]
Time Complexity
PreprocessingO(n)
Range QueryO(1)
Usage:
Extremely useful for scenarios where the array is static but strict range sum queries are frequent.