Sparse Table -Range Query Technique
Hey Guys, If you are a problem solver, you face some problem that requires new algorithms to solve that problem in the most optimal way. One day I was giving a codeforces contest, I faced a problem named “ Integer with friends”.To solve this problem, a Binary search and Range query on GCD was solved by either segment Tree or sparse Table. But I solved that problem using a sparse Table.
What is a sparse Table?
Sparse Table is a data structure that helps answer the range query problem in O(log N) time for each query and its real power show in computing Range minimum query in O(1) time complexity. We can’t apply this algorithm on immutable arrays i.e we can’t update an array over the range.
Note:- Sparse table is applied for a non-inverted operation like max, min, gcd, etc.
The main Intuition behind this algorithm is that we can express any non -negative integer as a sum of decreasing power of 2. For example 7 =2² +2¹+2⁰. Here we represent the 7 as a sum there requires 3 operations i.e log7 with base 2.By the same reasoning any interval can be uniquely represented as a union of intervals with lengths that are decreasing powers of two. E.g. [2,14]=[2,9]∪[10,13]∪[14,14][2,14]=[2,9]∪[10,13]∪[14,14], where the complete interval has length 13, and the individual intervals have the lengths 8, 4 and 1 respectably. And also here the union consists of at most [log2(length of the interval)]many intervals. The main idea behind Sparse Tables is to precompute all answers for range queries with a power of two lengths.
Suppose we have given an array of length n we have to break the array into a block of power of 2. For each index “i” we can create maximum size 2^i blocks less than equal to N.
2^i ≤N,
i≤logN blocks. If we are standing on the ith index of the array we can create almost logN blocks.That is the reason we require logN time complexity for each query.
Suppose we have given an array and we have to calculate the sum of the array over the range L and R . Here we will use the sparse table to precompute all answers for range queries with the power of two lengths.Let’s the range [3,10] =[3,3+2³-1] we can iterate over the array from index (i , i+2^j-1).In the range of [3,10] , the size of range is 8 so we can make maximum 2³ size of block .i.e [3,6],[7,10] which means that the range [i,i+2j−1][i,i+2j−1] of length 2^j splits nicely into the ranges[i,i+2^(j−1)−1]and[i+2^j−1,i+2j−1], both of length 2^(j-1).
Preprocessing
The construction of a sparse table is a very simple technique. You initialize the base of the table that is st[i][0] with the same values.
for (int i = 0; i < N; i++)
st[i][0] = array[i];
for (int j = 1; j <= K; j++)
for (int i = 0; i + (1 << j) <= N; i++)
st[i][j] = st[i][j-1]+st[i + (1 << (j - 1))][j - 1];Time complexity of preprocessing is O(N*logN).
Range Sum Queries
To answer the sum query for the range [L,R], we iterate over all powers of two, starting from the biggest one. As soon as a power of two 2^j is smaller or equal to the length of the range (=R−L+1), we process the first the first part of range [L,L+2^j−1], and continue with the remaining range [L+2^j,R].
long long sum = 0;
for (int j = K; j >= 0; j — ) {
if ((1 << j) <= R — L + 1) {
sum += st[L][j]; L += 1 << j; }
}
Time complexity for sum query is O(k).
Question :- solve CSES problem of Range Query Section.
