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.
Precomputation code
QueryCode
Thanking you in advance !
You're splitting R-L+1 into a bunch of powers of 2, but you're querying "[L, L + 2^i — 1]" every time; you need to query "[L, L + 2^i_1 — 1]" then "[L + 2^i_1, L + 2^i_1 + 2^i_2 — 1]" and so on.