Back to Study Material Data Structures and Algorithms

Prefix Sum

A prefix sum array is a preprocessing technique that transforms an input array into a new array where each element stores the sum of all input elements fro...

Prefix Sum

Precomputing Cumulative Totals to Answer Range Queries in O(1)

A prefix sum array is a preprocessing technique that transforms an input array into a new array where each element stores the sum of all input elements from index zero up to that position. Once this prefix array is built, any range sum query, asking for the sum of elements from index L to index R, can be answered in constant time.

Building the prefix array: given an input array A of n elements, create an array P of the same size. Set P[0] equal to A[0]. For each subsequent index i from one to n minus one, set P[i] equal to P[i minus one] plus A[i]. This single pass costs O(n) time and O(n) space.

To answer the range sum query for indices L to R: if L is zero, the answer is simply P[R]. If L is greater than zero, the answer is P[R] minus P[L minus one]. This subtraction removes the sum of elements before index L, leaving only the sum of elements from L to R. The query is answered in O(1) time after the O(n) preprocessing step.

This technique is powerful when many queries must be answered on the same array. Without prefix sums, each query requires O(R minus L plus one) time. With prefix sums, k queries cost O(n) preprocessing plus O(k) for the queries, a total of O(n plus k) rather than O(n times k).

Prefix sums extend to two dimensions. A 2D prefix sum array P where P[i][j] stores the sum of all elements in the sub-matrix from (0,0) to (i,j) allows any rectangular sub-matrix sum to be answered in O(1) after O(n times m) preprocessing using the inclusion-exclusion principle.

Prefix sums also appear in difference arrays for range update problems. If you need to add a constant value to every element in a subarray from L to R, performing each update directly costs O(n) per update. With a difference array, each update costs O(1), and you reconstruct the final array with a prefix sum pass in O(n) at the end.

Worked example: given an array of daily temperatures for a year (365 elements), answer ten thousand queries each asking for the average temperature in a given month range. Brute force would cost O(n) per query, total O(n times k). With prefix sums, preprocessing is O(365) and all ten thousand queries together cost O(10000), a massive speedup.

Interview tip: whenever you see multiple range sum or range average queries on a static array, immediately think prefix sum. It is one of the most frequently applicable precomputation techniques in competitive programming and interviews.