Блог пользователя nikhil_vaibhav_17

Автор nikhil_vaibhav_17, история, 3 года назад, По-английски

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 !

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.