Lowest Common Ancestor Queries

Let T be a rooted tree. The lowest common ancestor of any pair of nodes u_i,u_j in T is their common ancestor that is farthest away from the root.


For example, in the graph shown in this figure, the lowest common ancestor of u6 and u10 is u3.


In the lowest common ancestor queries problem, given a tree you need to pre-process the information such as to provide O(1) per-query answers to the question "What is the lowest common ancestor" of nodes ui and uj for any i,j in [n].
Assume for simplicity that the tree is a binary tree.
Then construct the following structures:


-An array E[1..2n-1] that stores the nodes of T in the order in which they occur in the Euler leftmost-way tour of the "double-tree" obtained from doubling each edge of T, starting at the root.


-An array L[1..2n-1] such that L[i] stores the level of node E[i].


-An array R[1..n] such that R[i] is the smallest integer l for which E[l] = ui.


Then for a given pair i, j assuming R[i] < R[j]. Let k be the integer such that R[i] ≤ k ≤ R[j] and L[k] is minimum. Then the lowest common ancestor of nodes ui and uj is equal to E[k].


Finding L[k] that is minimum for the subarray L[i..j] can be done in O(1) time if you apply the O(n log n) preprocessing used in this post to find the range minimum queries problem.


MArio

Range minimum problem (general case)

The Range Minimum Problem is defined as: Given an array A[1..n] of real numbers, we want to preprocess A such that for any two given integers i and j with 1 ≤ i < j ≤ n we can efficiently compute an integer k, i ≤ k ≤ j for which A[k] is minimum.


Here I am going to go over three solutions which use preprocessing to provide a O(1) per query operational time.


Solution 1:
This is the most brute of the three solution. It takes O(n^2) time and space.
It consists in storing the answer for all possible n-choose-2 pairs of (i,j) possible.
For this we make a two dimensional array X defining X[i][j] as:


X[i][j] = k ∈ [i,j] s.t. A[k] is minimum.


We construct X as shown in the recurrence relation shown in this figure.


Solution 2:
This solution is slightly smarter and takes O(n log n) time and space.
Here an array Y is defined as follows:


Y[i][l] = k ∈ [i, i + 2^l - 1] s.t. A[k] is minimum, for i∈[1,n-1] and l∈[1, log(n-i+1)]


For ease of exposition, by log(x) we mean floor of log(x) in this post.


Observe that for integers i and j in the interval [1,n] such that i < j, for h = log(i-j) we have that {i,i+1,...,i + 2^h - 1} ∪ {j - 2^h + 1,...,j} = [i,j].


Then min(A[Y[i][h]], A[Y[j-2^h+1][h]]) is the minimal element in A[i..j].


We construct Y as shown the recurrence relation in this figure.


All for now folks.


MArio