Range sum queries on arrays arise often in coding interviews and sw development.
They answer to the question of which is the sum of the values in any subarray.
This how to perform them efficiently: {1/8} ↓
They answer to the question of which is the sum of the values in any subarray.
This how to perform them efficiently: {1/8} ↓
Let's assume that the array values are never updated between the queries.
In such scenario, it's possible to preprocess the array and calculate range sum queries efficiently.
The approach is easier to grasp for 1D arrays, but it can be generalized to higher dimensions.
{2/8}
In such scenario, it's possible to preprocess the array and calculate range sum queries efficiently.
The approach is easier to grasp for 1D arrays, but it can be generalized to higher dimensions.
{2/8}
Given an array of n integers A[0,..,n], let's suppose we want to calculate the query Q(i,j).
Here Q(i,j) is the sum of the elements of A between the indices i and j with i <= j.
The naive approach to compute Q(i,j) is to iterate from A[i] to A[j] and sum the elements.
{3/8}
Here Q(i,j) is the sum of the elements of A between the indices i and j with i <= j.
The naive approach to compute Q(i,j) is to iterate from A[i] to A[j] and sum the elements.
{3/8}
Unfortunately the naive way takes linear time.
We can get a better complexity preprocessing the array and constructing a prefix sum array.
Such array has a nice property: its values are equal to the sum of the values in the original array up to the corresponding index.
{4/8}
We can get a better complexity preprocessing the array and constructing a prefix sum array.
Such array has a nice property: its values are equal to the sum of the values in the original array up to the corresponding index.
{4/8}
So given our array A[0,..,n], its prefix sum array is the array P[0,..,n] such that:
- P[i] is equal to the sum of the elements between A[0] and A[i].
The prefix sum array is built in linear time and space, but it makes possible to do range sum queries in constant time.
{5/8}
- P[i] is equal to the sum of the elements between A[0] and A[i].
The prefix sum array is built in linear time and space, but it makes possible to do range sum queries in constant time.
{5/8}
Indeed the following formula can be applied:
- Q(i,j) = P[j] - P[i-1]
where P[i-1] = 0 for i = 0.
An example can help to clarify.
{6/8}
- Q(i,j) = P[j] - P[i-1]
where P[i-1] = 0 for i = 0.
An example can help to clarify.
{6/8}
With A = [1,6,5,4,8,3,4,2,1,5], the prefix sum array become P = [1,7,12,16,24,27,31,33,34,39]
The range sum query Q(4,7) computed using A is Q(4,7) = 8+3+4+2 = 17
The same query computed using P is Q(4,7) = P[7] - P[3] = 33-16 = 17
{7/8}
The range sum query Q(4,7) computed using A is Q(4,7) = 8+3+4+2 = 17
The same query computed using P is Q(4,7) = P[7] - P[3] = 33-16 = 17
{7/8}
The approach generalizes also to higher dimensions.
A 2D prefix sum array can be used to calculate the sum of any rectangular subarray in costant time.
Each value in such array corresponds to the sum of the rectangular subarray starting at the upper-left corner.
{8/8}
A 2D prefix sum array can be used to calculate the sum of any rectangular subarray in costant time.
Each value in such array corresponds to the sum of the rectangular subarray starting at the upper-left corner.
{8/8}
Thanks for reading!
I'm Franco Fernando and I often write about algorithms and data structures.
If you enjoyed this read
✓ drop a comment
✓ leave a like or retweet
✓ follow me (@franc0fernand0) for similar content
I'm Franco Fernando and I often write about algorithms and data structures.
If you enjoyed this read
✓ drop a comment
✓ leave a like or retweet
✓ follow me (@franc0fernand0) for similar content
Loading suggestions...