Optimized Binary Lifting Technique!!

Revision en2, by EyadBT, 2023-10-14 00:27:46

Hello Codeforces!

Me and my friend JaberSH1 are glad to introduce this technique to the CP community since maybe only a few people know about it, personally me and Jaber worked on it and we haven't heard/read about such a thing before.

What can it do?

$$$K$$$-th ancestor & $$$LCA$$$ queries in $$$O(N*log(log(N))/2)$$$ preprocessing, and $$$O(log(log(N))$$$ per query.

Prerequisites:

  • Tree basics
  • Heavy-Light Decomposition
  • Binary Lifting

Ok let's get into it,

Tags tree, binary lifting, lowest common ancestor, hld, lca

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English EyadBT 2023-10-14 14:21:07 87 Tiny change: 'below:\n\n.\n.\n.\n\nLet's ' -> 'below:\n\n![ ](https://ibb.co/84g3D3Z)\n\nLet's ' (published)
en3 English EyadBT 2023-10-14 13:56:34 9160 Tiny change: 'O(1)$.\n\n$LCA$ queries:\n\nusing ' -> 'O(1)$.\n\n**$LCA$ queries:**\n\nusing '
en2 English EyadBT 2023-10-14 00:27:46 2 Tiny change: 'r:JaberSH1,2023-10-14] are glad' -> 'r:JaberSH1] are glad'
en1 English EyadBT 2023-10-14 00:22:36 530 Initial revision (saved to drafts)