EasyHigh Frequency20 min
Prefix Sum
Answer range sum queries in O(1) after O(n) preprocessing using cumulative sums.
Precompute cumulative sums in O(n). Then answer any range-sum query in O(1): rangeSum(l,r) = prefix[r+1] - prefix[l].
Prefix Sum
Operations — Step by Step
Build Prefix Array
O(n)prefix[0]=0 sentinel handles subarrays from index 0Step-by-step1 / 6
prefix[0] = 0
Sentinel. Sum of zero elements = 0.