Least Common Ancestor and Range Min Queries Explained

Least Common Ancestor and Range Min Queries Used some slides prepared by Dvir Halevi

This lecture discusses two closely related problems: Lowest Common Ancestors (LCA) and Range Min Queries (RMQ)

The LCA Problem Given a tree T with nodes numbered 0, 1, 2, , n-1 we want to preprocess it so that we can answer the queries of the form: LCAT(I,j) : Compute the lowest common ancestor (LCA) of i and j in T. This is the unique node in the tree that is the ancestor of both i and j, and farthest from the root of the tree T. For example, LCAT(4,7) = 2, and LCAT(6,0) = 0.

The RMQ Problem Given an array A[0], A[1], , A[n-1] preprocess it so we can answer queries of the following form: RMQT(I,j) : Compute an index k in [i,j] where A attains its minimum value. i.e. A[k] = min{A[i], A[i+1], , A[j]}. We present two solutions to the RMQ problem Solution 1: Preprocessing time and space O(nlogn); query O(1) Solution 2: (Special case) Preprocessing time and space O(n); query O(1) In the special case of the RMQ problem each successive elements of A differs from the previous one by 1.

How to reduce LCA to RMQ An Euler tour of a rooted tree visits the vertices in a specific order <visit the root, visit the first subtree (recursively); then visit the root; visit the second subtree (recursively); visit the root; .>. It ends with a visit to the root. The Euler tour of this tree visits the node following order E: <0,1,0,2,3,4,3,2,5,6,5,7,5,2,0>

How to reduce LCA to RMQ The Euler tour of this tree visits the node following order E: <0,1,0,2,3,4,3,2,5,6,5,7,5,2,0> Lemma: Let T be a rooted tree, and let E be the Euler tour of T. Let i and j be the two indices into the Euler tour. Then LCAT(E[i],E[j]) occurs in the Euler tour between i and j.

How to reduce LCA to RMQ We construct three arrays. E: Euler tour L: depth of each node in the Euler tour array H: first occurrence array; H[i] is the index of the first occurrence of i in the Euler tour.

How to reduce LCA to RMQ We first build the RMQ data structure on L. LCAT[u,v] is going to be the shallowest (closest to the root) node of the range [H[u] .. H[v]] of the Euler tour. LCAT[u,v] = E[RMQL(H[u],H[v]). (assuming w.o.l.g H[u] H[v])

An <O(nlogn,O(1)> Solution to RMQ The algorithm described here is called sparse table method. The input is A[0, 1, 2, , n-1]. We compute a 2-D table M[0 n-1][0 ceiling(log2n)] M[i][j] = The index of a minimum value in A[i i + 2j-1]. This is the answer to the RMQ for a range of length 2jfrom i.

An <O(nlogn,O(1)> Solution to RMQ Here is a recurrence we can use to compute this table in O(1) time per entry. Note that M[i][j] will only be needed if i + 2j-1 n-1. M[i][j] = i if j = 0; else If j > 0, let m1= M[i][j-1] and m2= M[i + 2j-1][j-1]. if A[m1] A[m2], M[i,j] = m1 else M[i,j] = m2. i + 2j-1 i + 2j-1 2j-1 2j-1 i i + 2j-1-1 m2 m1 This gives us the solution to a RMQ when the length of the query is a power of 2. Preprocessing cost O(nlogn); space = O(nlogn) Query time is O(1).

An <O(nlogn,O(1)> Solution to RMQ For arbitrary lengths we can compute the answer with just two look ups. RMQA(i,j) Let k = floor(log2(j-i+1). Let m1 = M[i][k]; m2 = M[j-2k+1][k] If A[m1] A[m2] then output m1 else output m2. Th solution overall is O(nlogn) space and time, and query cost is O(1).

Faster RMQ Use a table-lookup technique to precompute answers on small subarrays, thus removing the log factor from the preprocessing. Partition A into blocks of size . log n 2 log n n 2 A 2n blocks ... ... ... ... ... log n log log log n n n 2 2 2 12

Faster RMQ 2 n A [1,.., A [i] is the minimum element in the i-th block of A. ] log n 2 n ] B [i] is the position (index) in which value A [i] occurs. B[1,.., log n A 2n A [0] A [i] A [2n/logn] blocks ... ... ... ... ... log n log n 2 ... B[i] 13 B[0] B[2n/logn]

Example: n=16 A[] : 8 0 1 2 3 4 5 6 7 9 10 11 12 13 14 15 10 25 22 7 34 9 2 26 33 12 24 43 5 11 19 27 2n blocks 10 25 = 8 22 7 34 9 log n B[] : 0 1 2 A [] : 0 1 2 0 3 5 10 7 9 14

Faster RMQ Recall RMQ queries return the position of the minimum. LCA to RMQ reduction uses the position of the minimum, rather than the minimum itself. Use array B to keep track of where minimas in A came from. 15

Faster RMQ Preprocess A for RMQ using ST algorithm. ST s preprocessing time O(nlogn). 2 n A s size log n 2 2 n n = log( ) ( ) O n ST s preprocessing on A : ST(A ) = log log n n ( ), (1) O n O 16

Faster RMQ Having preprocessed A for RMQ, how to answer RMQ(i,j) queries on A? i and j might be in the same block -> preprocess every block. i < j on different blocks, answer the query as follows: 1. 2. 3. Compute minima from i to end of its block. Compute minima of all blocks in between i s and j s blocks. Compute minima from the beginning of j s block to j. Return the index of the minimum of these 3 values. 17

Faster RMQ i < j on different blocks, answer the query as follows: 1. Compute minima from i to end of its block. 2. Compute minima of all blocks in between i s and j s blocks. 3. Compute minima from the beginning of j s block to j. 2 Takes O(1) time by RMQ on A . 1 & 3 Have to answer in-block RMQ queries We need in-block queries whether i and j are in the same block or not. 18

Faster RMQ First Attempt: preprocess every block. log = log n n Per block : log (log loglog ) n O n 2 2 All blocks log n 2 n ( loglog ) O n n Second attempt: recall the LCA to RMQ reduction RMQ was performed on array L. What can we use to our advantage? 1 restriction 19

Faster RMQ Observation: Let two arrays X & Y such that Then , i j RMQ ( , ) = Y[i] C + X[i] i = ( , ) i j RMQ i j X Y A[0] A[1] A[2] A[3] A[4]A[5] A[6] A[7] A[8] A[9] 3 4 5 6 5 4 5 6 5 4 B[3] B[4]B[5] B[6] B[7] B[8] B[0] B[1] B[2] B[9] 0 1 2 3 2 1 2 3 2 1 +1 +1 +1 -1 -1 +1 +1 -1 -1 = log n 1 2 2 ( ) O n There are normalized blocks. ( ) O n 20

Faster RMQ Preprocess: Create tables of size queries. Overall . 2 ( ) (log O n = ) O n O ) n to answer all in block ( 2 log ( ) O n n For each block in A compute which normalized block table it should use ( ) O n ( ) O n Preprocess A using ST - Query: Query on A Query on in-blocks (1) O (1) O ( ), (1) O n O Overall RMQ complexity - 21