RANGE QUERY with Sparse Table (ST) algorithm

RANGE QUERY with Sparse Table (ST) algorithm.cpp

RANGE QUERY

Given a (big) array r[0..n-1], and a lot of queries of certain type. We may want to pre-process the data so that each
query can be performed fast. In this section, we use T (f, g) to denote the running time for an algorithm is O(f(n)) 
for pre-processing, and O(g(n)) for each query.

If the queries are of type getsum(a, b), which asks the sum of all the elements between a and b, inclusive, 
we have a T (n, 1) algorithm: Compute s[i] to be the sum from r[0] to r[i-1], inclusive, then getsum(a,b) simply 
returns s[b+1]-s[a].

RANGE MINIMUM QUERY
For the queries of the form getmin(a,b) asks the minimum elements between r[a] and r[b], inclusive, the task is 
little more hard. The idea is always to get the min in some big ranges, so in the queries we may try to use these big
ranges to compute fast. One simple algorithm is T (n,sqrt(n)): Break the n numbers into sqrt(n) regions, each of size 
sqrt(n). Compute the champion for each region. For each query getmin(a,b), we go from a towards right to the nearest 
station (at most sqrt(n) steps), then go by at most sqrt(n) stations (big regions) to the nearest station before b, 
and from there go to b.

Sparse Table (ST) Algorithm

A better approach is to preprocess RMQ for sub arrays of length 2k using dynamic programming. We will keep an array
preProcess[0, N-1][0, logN] where preProcess[i][j] is the index of the minimum value in the sub array starting at i 
having length 2j. For example :

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]
  2	    4	    3   	1	    6	    7
For the above array the preProcess[1][0] = 1, preProcess[1][1]=2,preProcess[1][2]=3 and so on. Specifically, we find 
the minimum in a block of size 2j by comparing the two minima of its two constituent blocks of size 2j-1. More formally,
preProcess[i, j] = preProcess[i, j -1] if A[preProcess[i, j -1]] <= A[preProcess[i+2j-1, j -1]] and preProcess[i, j] = 
preProcess[i+2j-1, j -1] otherwise.

Once we have these values preprocessed, let’s show how we can use them to calculate RMQ(i, j). The idea is to select two 
blocks that entirely cover the interval [i..j] and  find the minimum between them. We select two overlapping blocks that
entirely cover the subrange: let 2k be the size of the largest block that fits into the range from i to j, that is 
let k = log(j – i). Then rmq(i, j) can be computed by comparing the minima of the 
following two blocks: i to i + 2k – 1 (preProcess(i, k)) and j – 2k + 1 to j (preProcess(j -2k +1, k)). These values 
have already been computed, so we can find the RMQ in constant time.