Sparse Table Query Help

Правка en1, от nikhil_vaibhav_17, 2021-05-31 10:04:46

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 !

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский nikhil_vaibhav_17 2021-05-31 10:04:46 1625 Initial revision (published)