Range Sum Queries on Array in O(1) Time Complexity

Given an array A of N elements A₁, A₂, A₃ . . . A_N, we have to answer Q queries. In each query, we will be given two indices l and r, we have to compute the sum of elements from index l to r.

In general, each query will define a contiguous block of array and we have to compute the sum of all elements in this block, more commonly known as a sub-array.

In this situation, the time complexity of O(Q*N) will get us the Time Limit Exceeded verdict.

So, to answer the queries efficiently in least possible time, i.e., O(1) we can make use of prefix sums. A very simple observation along with prefix sums, help us to answer these queries efficiently. Prefix sums defines an array, which is computed in the following manner:

int pSum[N];  
pSum[0] = A[0];
for(int i=1; i<N; i++)
    pSum[i] = pSum[i-1] + A[i];

Here, pSum[i] can be defined as

 pSum[i] = A[0] + A[1] + A[2] +...+ A[i],  for 0 ≤ i ≤ N-1

This pre-computation of prefix sums takes O(N) time. This pre-computation enables us to answer each query in O(1) time.

Lets see an example,

Let A be an array of size N=10

A = [13, 6, 7, 23, 12, 11, 0, 19, 4, 20]

The array pSum will calculated as,

pSum = [13, 19, 26, 49, 61, 72, 72, 91, 95, 115]

Now if we are given a query as l=3 and r=8, i.e., we have to find the sum

This can be written as:

(A[0] + A[1] + A[2] + A[3] + A[4]+ A[5] + A[6] + A[7] + A[8]) – (A[0] + A[1] + A[2])

This is equal to,

In general, for a query (l,r) the sum of elements A[l] + A[l+1] + A[l+2] +...+ A[r] can be computed as

We may have a query in which l=0, in this case accessing pSum[l-1] will give rise to segmentation fault. So when l=0, we can directly return pSum[r].

In this way, we can answer all the Q queries in O(1) time with just O(N) time pre-computation of prefix sums. Thus the time complexity reduces to be O(N+Q).

Implementation in C++:

#include<iostream>
#include<vector>
using namespace std;

int main() 
{
    int N,Q;
    //reading the size of array and number of queries
    cin>>N>>Q;
    
    //declaring containers for array and prefix sum array
    vector<int> A(N), pSum(N);
    
    //reading the elements of array
    for(int i=0;i<N;i++)
        cin>>A[i];
        
    //computing the prefix sums
    pSum[0]=A[0];
    for(int i=1;i<N;i++)
        pSum[i]=pSum[i-1]+A[i];
    
    //queries
    while(Q--)
    {
        int l,r;
        //reading the l and r values of the range
        cin>>l>>r;
        
        //printing the output
        if(l==0)
            cout<<pSum[r]<<"\n";
        else 
            cout<<pSum[r]-pSum[l-1]<<"\n";
    }
}

Sample Input:
10 3
13 6 7 23 12 11 0 19 4 20
0 7
2 6
6 9

Sample Output:
91
53
43