SPOJ THRBL using Sparse Table

SPOJ THRBL : Catapult that ball is a pretty straightforward RMQ problem. I will formalize the problem in short below-

Given a array containing N integers, answer Q queries asking maximum element in the array lying within offset A and B.

Example:
Array = [8, 5, 3, 4, 7, 1, 9, 2, 6]
A = 1, B = 5 (0 based offset)
Then the subarray between A to B is [5, 3, 4, 7, 1] and the answer is 7.

You can study how to construct sparse table in this tutorial.

Defining entries in sparse table - ST[i][j] = maximum element in range [i, i+2^j]

The Sparse Table for above array will look like-

Once this table (call it ST) is constructed in O(n log n) time, you can answer queries in O(1) time.
Like for A=1, B=5 -

• First find the log base 2 of length of sub array. And subtract one from it. That is log(B-A+1) - 1 = log(5 - 1 + 1) - 1= 3 - 1 = 2. Let this quantity be L.
• Answer is simply maximum of ST[A][L], ST[B-2^L][L]

The customary code follows-

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

vector< int > v;
vector< vector< int > > st;

int log2(int x)
{
    int i=0;
    while (x){
        x>>=1;
        i++;
    }
    return i;
}

void constructsparsetable(int n)
{
    int c = log2(n);
    st = vector< vector< int > >(n, vector< int >(c));

    //Initialize
    for (int i = 0; i < n; i++){
        st[i][0] = v[i];
    }
    for (int i = 1; i < c; i++){
        for (int j = 0; j < (n - (1<<(i-1))); j++){
            st[j][i] = max(st[j][i-1], st[j+(1<<(i-1))][i-1]);
        }
    }
}

int querysparsetable(int a, int b)
{
    int l = log2(b - a + 1);
    return max(st[a][l-1], st[b-(1<<(l-1))][l-1]);
}

int main()
{
    int n, m, h, a, b;
    scanf("%d %d", &n, &m);
    v.reserve(n);
    for (int i = 0; i < n; i++){
        scanf("%d", &h);
        v.push_back(h);
    }

    constructsparsetable(n);

    int c = 0;
    for (int i = 0; i < m; i++){
        scanf("%d %d", &a, &b);
        if (querysparsetable(a, b-2) <= v[a-1])
            c++;
    }
    printf("%d\n", c);
}