LCA Problem Series
LCA ①) Linear LCA query
LCA ②) LCA query using Sparse Table
LCA ③) LCA query using Segment Tree
LCA ④) LCA reducted RMQ

1. Problem

  • Input: a rooted tree $T$ of $n$ nodes two nodes $u$, $v$ in $T$

  • Output: the least common ancestor of $u$, $v$

fig 1. LCA problem

  The Least Common Ancestor(LCA) is the well-know problem. LCA is the node furthest from the root that is an ancestor of both given nodes $u$ and $v$. The notation of LCA query of nodes $u$ and $v$ of $T$ is $LCA_T(u,v)$. In this problem, the ancestor of node $v$ includes $v$. For example, in figure 1, $LCA_T(7, 9)$ is node $4$. And, $LCA_T(2,6)$ is node $2$, because ancestor of node $2$ includes node $2$.



2. Sparse Table

fig 2. The outline of sparse table solution

  Sparse table is a well-known data structure, generally used to solve range query. Elements of a sparse table is a value of the $2^i$th information. In this solution, we construct sparse tables per nodes, and the $i$th element of the sparse table of node $w$ is the $2^i$th ancestor of node $w$. Precisely, there are $2^i$ edges in the simple shortest path between node $w$ and its $2^i$th ancestor. It makes the procedures of the Naive solution of LCA problem more faster.

fig 3. Sparse Table



3. Preprocessing

\[ST[i][j] = \mathrm{the} \; j \mathrm{th \; ancestor\; of\; node\; labeld} \; i\]

  Before solving the LCA problem, we have to construct a sparse table for each node. We can construct all sparse table in an array $ST$. Elements of a sparse table is a ancestor of a node. So, $ST$ is a matrix difined as the fomula above and figure 3.,

fig 4. The Property of Sparse Table

  Intuitively, construction of $ST$ seems to take a long time. However, because of property of sparse table, $ST[i][j]$ is same with $ST[ST[i][j-1]][j-1]$. So, construct sparse table, while traveling nodes by in-order traversal. To determine $ST[i][j]$, we look-up the sparse tables(Memoization - Dynamic programming). Note that the first ancestor of a node is itself by the difinition of ancetor. In sparse tables, $ST[i][0]$ is the parent of node $i$.



4. Query

  1. If $u$ is the node whose depth is greater than another, go up until the depth is the same as the depth of the other nodes. If $floor(log2(u.depth))$ is $maxD_u$, check ancestors from $ST[u][maxD_u]$ to $ST[u][0]$ until finding $ST[u][j]$ whose depth is more than the depth of $v$. If $ST[u][j]$ is greater than the depth of $v$, check ancestors of $ST[u][j]$ from $ST[ST[u][j]][j-1]$ to $ST[ST[u][j]][0]$ in same deadline. This iteration runs recursively. Change $u$ to the found ancestor whose depth is same with the depth of $v$.
  2. Check ancestors of $u$ and $v$ from $ST[u][maxD_u]$, $ST[v][maxD_v]$ to $ST[u][0]$, $ST[v][0]$. In the iteration, if $ST[u][j] \neq ST[v][j]$ is occur, change $u$, $v$ to $ST[ST[u][j]]$, $ST[ST[v][j]]$. After that, run the iteration recursively in a same manner to the first procedure.
  3. Because the second procedure returns a child of LCA of $u$, $v$, we can get LCA from the return node.

  The method of LCA query is same with the naive solution. However, in the solution of sparse tree, the process of finding the ancestor is performed in a similar manner to binary search, not one node by one.

fig 4. The Property of Sparse Table in LCA query

  The manner of the first procedure and the second procedure looks like binary search. Note that we changed $ST[u][j]$ to $ST[ST[u][j]][j-1]$ in both procedure. Because $ST[ST[u][j]][j]$ is equal $ST[u][j+1]$, we don’t need to check the node again.   In the second procedure, $ST[u][j] \neq ST[v][j]$ means the ancestors of $u$, $v$ are still under LCA. If the ancestors of $u$, $v$ is same, they are over LCA because the ancestor of $u$, $v$ over LCA is common ancestors.



5. Complexity

  • Time Complexity:
    • preprocessing time: $O(n \log{n})$
    • query time: $O(\log{n})$
  • Space Complexity: $O(n\log{n})$

  There is $n$ nodes and the size of a sparse table of a node is $O(\log{n})$. So, preprocessing time complexity and space complexity is $O(n\log{n})$. And, in a query, we can find LCA in $O(\log{n})$ time. We can derive intuitively the time complexity by binary search.

Refers

Crocus, “LCA(Lowest Common Ancestor) 알고리즘”



Prev: LCA ①) Linear LCA query

Next: LCA ③) LCA query using Segment Tree