Hello Everyone,

I am currently learning about sparse table. So after learning basics , I tried to implement it on my own. I thought that it should but I am not able to figure out why it is not working.

So I built table sparse[N][26] , sparse[i][j] gives minimum of the range (i , i + pow(2,j) — 1). Now the problem is :

For a given query range [L , R] , the length of range is R — L + 1. We can represent it as a sum of powers of two so I run a loop for iterating bits and if a bit is set , I made a jump of length pow(2,j) from L. It did not worked for all test cases.

Then I learnt about idempotency and then solved the problem using it. But I want to know why the previous approach is not working.

const int MAXN = 1e5+1;
int sparse[MAXN][26];
void pre(int n , vi &a) {
    
    for(int i=0; i<n; i++) sparse[i][0] = a[i];
    
    for(int j=1; (1<<j) < n ; j++) {

        for(int i=0; (i + (1<<j) - 1) < n; i++) {

            sparse[i][j] = min (sparse[i][j-1] , sparse[i+(1<<j-1)][j-1]);

        }

    }
    
}

    int q;
    cin >> q;
    
    while(q--) {
        
        int l , r;
        cin >> l >> r;
        
        int j = r-l+1;
        int ans = INT_MAX;
        
        for(int i=0; i<32; i++) {
            if(j & (1<<i)) 
                ans = min(ans , sparse[l][i]);
        }
        
        cout << ans << "\n";
    }

Thanking you in advance !