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

Please help me to understand binary raise used in this problem .
Автор 3_Problems_Everyday, история, 9 лет назад, По-английски

Hello everyone ! I am trying to solve this problem.I didn't understand the editorial properly. Please help me to understand the binary raise used in the editorial. Because i am new to this concept, provide me some tutorial to learn it.Thanks :)

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

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

Looks like it refers to the Sparse Table structure complementary to the LCA algorithm. The author may have used this name because the Sparse Table indexes are equivalent to powers of two ("binary raises")

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I believe binary raise refers to "skips" of power of two used in the LCA algorithm. For LCA, we store for each node, the nodes at distances 1, 2, 4, 8... and so on, going to the root. That way we'll be able to answer queries in logarithmic time. I think the editorial is pretty clear to understand the rest of the problem (dealing with different cases). The pictures are very helpful.

Refer to my code if it helps -> C++ Code

→ Ответить