[Tutorial] Optimized Binary Lifting Technique

Revision en4, by EyadBT, 2023-10-14 14:21:07

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)))$$$ preprocessing, and $$$O(log(log(N))$$$ per query.

Prerequisites:

  • Tree basics
  • Heavy-Light Decomposition
  • Binary Lifting

Ok let's get into it,

$$$K$$$-th ancestor queries:

Given a tree of $$$N$$$ vertices, let's build the HLD chains. For each chain, we are going to store its vertices in an array such that we can reach them by index. Let's take a vertex $$$u$$$, now we want the $$$K$$$-th ancestor of $$$u$$$. It's easy to look it up walking up the chains until we reach the chain with the maximum-depth top vertex for which its depth is less than or equal to $$$depth_u - k$$$. This operation costs $$$O(log(N))$$$ since we only change the chain we are in when the subtree size doubles up. Now imagine another tree containing only the light edges of our original tree, its depth is going to be less than or equal to $$$log(N)$$$. This is equal to adding $$$smart$$$ edges between the top vertices of the chains, each top vertex connected to the top vertex of the chain of its parent. See the picture below:

Let's build a binary lifting array over this compressed tree. Since its depth is not more than $$$log(N)$$$ then we will store only $$$log(log(N))$$$ info for each top vertex. Ok, now back to the $$$K$$$-th ancestor query, we can binary lift to the chain with the minimum-depth for which its depth is bigger than $$$depth_u - k$$$, this operation costs $$$O(log(log(N)))$$$. Our required vertex is going to be in the parent chain of this chain and we can reach it by index in $$$O(1)$$$.

$$$LCA$$$ queries:

Using the same technique, we can get the $$$LCA$$$ of two nodes $$$u$$$, $$$v$$$ in $$$O(log(log(n)))$$$ time complexity, we will store for each chain in the HLD tree the depth of the chain (how many chains above it), now if we consider node $$$u$$$ has a chain with higher depth than the chain of node $$$v$$$, we will try to lift node $$$u$$$ to be in a chain with the same depth of the chain of node $$$v$$$. to do this, we will have to find the chain with depth equal to the depth of the chain of $$$v$$$ plus $$$1$$$, and then we will go to the parent of the top node of that chain so now, node $$$u$$$ and $$$v$$$ have the same chain depths, and if they are in the same chain then it's easy to see that the higher node is the $$$LCA$$$. Otherwise, we will lift both chains of $$$u$$$ and $$$v$$$ as long as the head of the chains differ, after we lift the chains, the parent of the chain with the highest top node should be the $$$LCA$$$.

Jaber's code:
My code:
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)