Prefix Sum -Introduction (Range Sum Query)

Prefix Sum – Introduction and Range Sum Query

A prefix sum is a preprocessing technique used to calculate the sum of elements across multiple ranges efficiently.

For an array, each prefix sum stores the cumulative sum of elements from the beginning of the array up to a particular position. Once this information is prepared, the sum of any continuous range can be calculated without traversing that range again.

Consider:

arr = [2, 4, 1, 3, 5]

The cumulative sums are:

2, 6, 7, 10, 15

Here:

• The sum of the first element is 2.

• The sum of the first two elements is 2 + 4 = 6.

• The sum of the first three elements is 2 + 4 + 1 = 7.

• The process continues until the complete array has been included.

Prefix sums are particularly useful when the array remains unchanged and multiple range-sum queries must be answered.

Range Sum Query

Given an array of N integers and multiple queries, each query provides two indices L and R.

For every query, find the sum of all elements from index L to index R, both inclusive.

The indices satisfy:

0 ≤ L ≤ R < N

Example

Consider:

arr = [2, 4, 1, 3, 5]

Queries:

• [1, 3]

• [0, 2]

• [2, 4]

For query [1, 3]:

4 + 1 + 3 = 8

For query [0, 2]:

2 + 4 + 1 = 7

For query [2, 4]:

1 + 3 + 5 = 9

Therefore, the answers are:

[8, 7, 9]

Why Is Prefix Sum Needed?

Without preprocessing, every range query can be answered by traversing from index L to index R and adding the elements.

For a single query, this may take O(N) time in the worst case.

If there are Q queries, the total time complexity can become:

O(N × Q)

For a large array and many queries, repeatedly calculating the same partial sums is inefficient.

Prefix sum calculates the cumulative information once in O(N) time. After that, each range-sum query can be answered in O(1) time.

The total time becomes:

O(N + Q)

where:

• O(N) is required to build the prefix sum.

• O(Q) is required to answer all queries.

Constructing the Prefix Sum Array

A convenient method is to create a prefix sum array of size N + 1.

Let:

prefix[0] = 0

For every array index i:

prefix[i + 1] = prefix[i] + arr[i]

Using:

arr = [2, 4, 1, 3, 5]

The prefix sum array becomes:

prefix = [0, 2, 6, 7, 10, 15]

Each prefix[i] stores the sum of the first i array elements.

The initial 0 makes every range query follow the same formula, including ranges that begin at index 0.

Algorithm

• Create a prefix sum array of size N + 1 so an initial zero can be stored.

• Set prefix[0] to 0 because no array element has been included yet.

• Traverse the original array from left to right.

• Add the current array element to the previously calculated prefix sum.

• Store the result at the next position of the prefix array.

• Continue until every array element has contributed to the cumulative sum.

Time Complexity: O(N) because every array element is processed once.

Space Complexity: O(N) because an additional prefix sum array is maintained.

Answering a Range Sum Query

To calculate the sum from index L to index R, use:

Range Sum = prefix[R + 1] - prefix[L]

The value prefix[R + 1] contains the sum of all elements from index 0 to index R.

The value prefix[L] contains the sum of all elements before index L.

Subtracting these unwanted elements leaves only the required range.

Example

Consider:

arr = [2, 4, 1, 3, 5]

prefix = [0, 2, 6, 7, 10, 15]

Find the sum from:

L = 1 to R = 3

The required elements are:

[4, 1, 3]

Using the prefix sum formula:

Range Sum = prefix[R + 1] - prefix[L]

Range Sum = prefix[4] - prefix[1]

Range Sum = 10 - 2

Range Sum = 8

Therefore, the sum of elements from index 1 to index 3 is 8.

Algorithm

• Receive the left boundary L and right boundary R of the query.

• Use prefix[R + 1] to obtain the sum from index 0 through index R.

• Use prefix[L] to obtain the sum of all elements before index L.

• Subtract the second value from the first to remove the unwanted prefix.

• Return the remaining value as the sum from index L to index R.

Time Complexity: O(1) for each query because only two prefix values are accessed.

Space Complexity: O(1) auxiliary space for answering a query because no additional structure is created.

Why Does the Range Sum Formula Work?

The value:

prefix[R + 1]

contains:

arr[0] + arr[1] + ... + arr[L - 1] + arr[L] + ... + arr[R]

The value:

prefix[L]

contains:

arr[0] + arr[1] + ... + arr[L - 1]

After subtraction, every element before index L is cancelled:

prefix[R + 1] - prefix[L]

The remaining elements are:

arr[L] + arr[L + 1] + ... + arr[R]

This is exactly the required range sum.

Query Beginning at Index 0

Consider the query:

L = 0, R = 2

Using:

prefix = [0, 2, 6, 7, 10, 15]

Apply the same formula:

Range Sum = prefix[R + 1] - prefix[L]

Range Sum = prefix[3] - prefix[0]

Range Sum = 7 - 0

Range Sum = 7

The extra initial zero allows queries beginning at index 0 to be handled without a separate condition.

Single-Element Range

When L = R, the query asks for the value at only one index.

For:

L = 2, R = 2

The formula gives:

prefix[3] - prefix[2]

7 - 6 = 1

This is equal to:

arr[2] = 1

Therefore, the same formula works for single-element ranges.

Complete-Array Range

For an array of size N, the complete range is:

[0, N - 1]

Its sum is:

prefix[N] - prefix[0]

Since prefix[0] = 0, the result is simply:

prefix[N]

Therefore, the last value of the prefix array stores the sum of the complete original array.

Alternative Prefix Sum Convention

Another common convention creates a prefix sum array of size N, where:

prefix[i] = arr[0] + arr[1] + ... + arr[i]

For:

arr = [2, 4, 1, 3, 5]

This produces:

prefix = [2, 6, 7, 10, 15]

The range sum is then calculated as:

• prefix[R], when L = 0

• prefix[R] - prefix[L - 1], when L > 0

This convention is valid, but it requires a separate condition for ranges beginning at index 0.

Using an array of size N + 1 with an initial zero avoids that special case. Either convention can be used, but the construction and query formula must remain consistent.

Brute Force and Prefix Sum Comparison

Prefix sum exchanges additional memory and one preprocessing pass for much faster range queries.

For only one query, direct traversal may be sufficient. Prefix sum becomes more valuable when many queries must be answered on the same unchanged array.

Prefix Sum with Negative Numbers

Prefix sums also work when the array contains negative numbers, zeros, or duplicate values.

Consider:

arr = [3, -2, 5, -1]

The prefix sum array is:

prefix = [0, 3, 1, 6, 5]

For the range [1, 3]:

prefix[4] - prefix[1]

5 - 3 = 2

The direct sum is:

-2 + 5 - 1 = 2

The technique depends on addition and subtraction, not on the elements being positive.

Handling Array Updates

A basic prefix sum is most suitable for a static array, where the values do not change after preprocessing.

Suppose one array element is updated. Every prefix sum after that position may also change, making the existing prefix array outdated.

Rebuilding the prefix sum takes:

O(N)

When both updates and range-sum queries occur frequently, more advanced data structures are usually preferred:

• Fenwick Tree: Supports point updates and range-sum queries in O(log N).

• Segment Tree: Supports different types of updates and range queries in O(log N).

Prefix sum remains preferable when the array is fixed and the number of queries is large.

Prefix Sum Beyond Range Sums

The prefix technique can store other cumulative information.

Prefix Frequency

A prefix frequency array can store how many times a value or condition has appeared up to each position.

It can answer queries such as:

• How many even numbers lie in a range?

• How many times does a character appear in a substring?

• How many elements satisfy a condition between two indices?

Prefix XOR

Prefix XOR stores the cumulative XOR of elements and can answer range-XOR queries using:

Range XOR = prefixXor[R + 1] XOR prefixXor[L]

Two-Dimensional Prefix Sum

For a matrix, a two-dimensional prefix sum stores the cumulative sum of rectangular regions.

It can answer rectangle-sum queries by combining four prefix values. This extends the same idea of adding the required region and removing the unwanted portions.

Difference Array

A difference array is closely related to prefix sums. It supports efficient range updates by storing how values change between neighbouring positions. A final prefix sum reconstructs the updated array.

When Should Prefix Sum Be Used?

Consider prefix sum when:

• Multiple range-sum queries must be answered.

• The queries involve continuous subarrays.

• The original array remains unchanged.

• Repeatedly traversing the same ranges is too expensive.

• Cumulative counts or frequencies are required.

• A problem asks for the sum between two indices many times.

• A condition over a range can be represented using cumulative information.

Advantages of Prefix Sum

• It answers each range-sum query in constant time after preprocessing.

• It avoids recalculating sums for overlapping ranges.

• It is simple to construct and apply.

• It works with positive numbers, negative numbers, and zeros.

• It can be extended to matrices, frequencies, XOR, and other cumulative operations.

• It is useful as a building block for more advanced techniques.

Limitations of Prefix Sum

• It requires additional O(N) space when a separate prefix array is used.

• A basic prefix sum does not efficiently support frequent updates.

• Incorrect index handling can cause off-by-one errors.

• Large cumulative values may exceed the selected numeric data type.

• It is mainly beneficial when multiple queries are performed.

• Not every operation supports removing a prefix as conveniently as addition or XOR.

Common Mistakes

• Confusing an array index with a prefix-array index.

• Using prefix[R] - prefix[L] for an inclusive range while following the N + 1 convention.

• Forgetting that the correct formula is prefix[R + 1] - prefix[L].

• Mixing the size-N and size-N + 1 prefix conventions.

• Forgetting that both L and R are included in the query.

• Reusing the prefix array after the original array has been modified.

• Using a numeric type that cannot store the maximum possible cumulative sum.

• Adding the elements again during each query instead of using the prepared prefix values.

• Ignoring invalid ranges where L > R or an index lies outside the array.

FAQs

Q1. What should be done if the array receives frequent updates along with range-sum queries?

A basic prefix sum becomes inefficient because an update may affect every later prefix value. A Fenwick tree or segment tree is more suitable because both updates and queries can be handled in O(log N) time.

Q2. Why is a prefix array of size N + 1 often preferred?

The additional position stores an initial zero. This allows every inclusive range [L, R], including ranges beginning at index 0, to use the same formula: prefix[R + 1] - prefix[L].

Q3. How should the numeric data type for a prefix sum be selected?

Consider the largest possible cumulative sum rather than only the largest individual element. If the array can contain N values of magnitude M, the prefix sum may reach approximately N × M, so a wider numeric type may be required.

Q4. Can prefix sum be used to find the sum of a circular range?

Yes. If the range does not wrap around, use the normal formula. If it crosses the end of the array, combine the suffix from L to N - 1 with the prefix from 0 to R.

Q5. How is the prefix-sum idea extended to a two-dimensional matrix?

A two-dimensional prefix array stores the sum of the rectangle from the matrix origin to each position. Any rectangular query can then be answered by adding the required cumulative region, subtracting the regions above and to the left, and adding back their overlapping portion.