You might have come across many problems in various contests where the problem statement requires you to find a sum,product or maximum within a range [ l,r] in an array of size N. This blog is all about the magic that happens from l to r.

A naive approach would be to traverse the list/array from index l to index r. This would give correct answer for each query. But the running time of this algorithm would be O(N). And if the number of queries Q is large the overall running time would be O(n*Q) and in the case where Q=n it’ll be running in O(n²) . This function grows really fast as n increases. Can we do better ?

Well we can try to store all possible [l,r] pairs and reference to them in O(1) time . Therefore each query is a constant time operation. The overall running time is O(Q) . But the space complexity is large . As the value of N increases the number of possible [l,r] pairs also increases. Soon we will run out of memory. The space complexity of this algorithm would be O(n²) :(

Some well known methods to do Range Based queries efficiently

  1. Segment Tree

Segment Tree

Segment tree is based on the concept of trees and that at each node we store some information about a range. These nodes further depend on the information stored within the nodes in the next layer.

Rewriting an explanation to this would be unnecessary since AI.Cash has already written one on it in Codeforces . Suggest you read about some bit manipulation if your new to it before reading this article.

With this data structure we can make all [l,r] queries in O(log(n)) time.Pretty awesome!

Fenwick Tree(Binary Indexed Tree)

This data structure was found by Peter M. Fenwick,this structure was first used for data compression. Now it is often used for storing frequencies and manipulating cumulative frequency tables.

The Basic idea is that each integer can be represented as sum of powers of 2. In the same way, ranges can be represented as sum of sets of sub ranges which are smaller(yeah this is a bit hard to understand at first).

This too has been explained in a great amount of detail on Topcoder. Check it out.

The above two techniques seem to be really hard to understand and something which seems like would have taken a lot of time to come up with.

Square Root decomposition

This algorithm involves the most amount of magic. This magic algorithm is only know to a very few people out there.

Lets write the solution for finding the sum for a query within a range [l,r].

These two functions insert() and remove() help find the sum from [l,r]. This can be done by calling insert(l),insert(l+1),insert(l+2)…..insert(r-1),insert(r)

The answer for this query can then be printed using answer. For a different range [l,r] we may need to remove/insert some elements to the answer variable which we used to compute the previous query.This is an O(N²) algorithm but slightly better. Since for some queries we need not go from l to r all the way. Example queries: [1,4] and [1,5] for the second query we simply append the 5th element to the answer if we have already processed the first query .

void insert(int pos)
{
cout<<endl<<”add “<<a[pos];
answer+=a[pos];
}
void remove(int pos)
{
cout<<endl<<”rem “<<a[pos];
answer-=a[pos];
}

Lets make this same code to better the algorithm and make it run in O(sqrt(N)*N) . It looks impossible looking at the code now right :P All we do in this algorithm is that we carefully reorder the queries asked or pick them from the list of queries carefully.

The magic Algorithm

  1. The first step is to divide the given list into sqrt(N) blocks. Therefore now each block contains sqrt(N) (N/sqrt(N)) elements within it.

example queries :

{0, 3} {1, 7} {2, 8} {7, 8} {4, 8} {4, 4} {1, 2}

step 1 blocks of size 3 are made

step 2 sort based on the blocks to which the queries belong to based on the starting index of each query.

{0, 3} {1, 7} {2, 8} {1, 2} {4, 8} {4, 4} {7, 8}

step 3 break ties within queries of the same block by considering the last index of each query

{0, 3} {1, 2} {1, 7} {2, 8} {4, 4} {4, 8} {7, 8}

This is the final ordering of queries. Process the Queries in this order and you’ll achieve O(N)

“Talk is cheap,show me the code”-Linus Torvalds

Create a structure

struct query
{
ll r,l;
};

Now in the main function

int i,n,t,q;
cin>>n;// number of elements within out list
while(n--&&(cin>>t))
a.push_back(t);
cin>>q;// Read the number of queriesquery qa[q];

for(i=0;i<q;i++)
cin>>qa[i].l>>qa[i].r;// read all queries
rootn=pow(a.size(),0.5);// find the number of blocks
sort(qa,qa+q,block);// now sort based on which block they belong
// resolve all conflicts by considering index r for each query

The block comparator function will look something like this

bool block(query a,query b)
{

if(floor(a.l/rootn)<floor(b.l/rootn))
return true;
else if(floor(a.l/rootn)>floor(b.l/rootn))
return false;
return a.r<b.r;
}

Now we process the query from the query list qa one by one and print the answer.

Maintain two varibles currentL and currentR. set them to zero . And update answer to a[0]

int currentL=0,currentR=0;
answer=a[0];

Now for a query [1,3] we need to move our currentL to 1 and currentR to 3. Right now we hold the answer for [0,0] so we must remove this from answer. remove(0) and update currentL similary we update currentR to 3. and insert(1) insert(2) insert(3). The answer now contains solution to query [1,3]. Now for a query from [1,2] we simply need to update the currentR to 2. So we now need to remove index 3 from answer remove(3) and update currnetR. Similary for all other cases.

for(i=0;i<q;i++)
{
while(currentL<qa[i].l)
remove(currentL),currentL++;
while(qa[i].l<currentL)
insert(--currentL);
while(currentR<qa[i].r)
insert(++currentR);
while(currentR>qa[i].r)
remove(currentR),currentR--;
cout<<"answer:"<<answer;
}

Time complexity

For each block, the queries are sorted in increasing order, so clearly the right pointer (currentR) moves in increasing order. During the start of next block the pointer possibly at extreme end will move to least qa[i].r in next block. That means for a given block, the amount moved by right pointer is O(N). We have O(Sqrt(N)) blocks, so the total is O(N * Sqrt(N)). Great!

Let us see how the left pointer moves. For each block, the left pointer of all the queries fall in the same block, as we move from query to query the left pointer might move but as previous qa[i].l and current L fall in the same block, the moment is O(Sqrt(N)) (Size of the block). In each block the amount left pointer moves is O(Q * Sqrt(N)) where Q is number of queries falling in that block. Total complexity is O(M * Sqrt(N)) for all blocks.

There you go, total complexity is O( (N + M) * Sqrt(N)) = O( N * Sqrt(N))

An O(N²) get converted into O(sqrt(N)*N) is something which still blows my mind :P

“Any sufficiently advanced technology is indistinguishable from magic.”

-Arthur C. Clarke

STAY HUNGRY.STAY FOOLISH.