2807853
| Question | Answer |
| Define the Lowest Common Ancestor Problem. I.e. what does LCA(i,j) return? | Given a preprocessed tree, and an i and j, find the lowest common ancestor of nodes i and j. |
| How is a Euler tour different to a depth first search? | Repeats are listed |
| How long is the Euler tour of a preprocessed LCA tree? | 2(n-1) |
| Describe how to preprocess a tree ready for an LCA query. | Construct N and D from T after an euler tour (where N stores nodes and D stores the depths of said nodes). Add a pointer from each node i to some N[i'] = i. Preprocess D for RMQs. |
| Describe how to make a LCA query when solved using RMQs. | Find any i' such that N[i'] = i. Find any j' such that N[j'] = j. Compute RMQ(i',j') in D. The LCA of i and j = N[RMQ (i', j') ] |
| Without using the +/- RMQ algorithm. What is the prep time, space and query time complexity of the LCA solution using RMQs? | Prep = O(nlogllogn) Space = O(nloglogn) Query Time = O(1) |
| If the +/- RMQ problem can be solved with O(n) space, O(n) prep time and O(1) query time, what is the space, prep time and query time complexity for LCAs when solved using the +/- RMQ algorithm? | O(n) space, O(n) prep time and O(1) query time. |
| How can RMQs be solved in O(1) query time and O(n) space/prep time? | Build the cartesian tree of the array A (for the RMQ problem), in O(n) time. The LCA in the tree equals the RMQ in A. |
Want to create your own Flashcards for free with GoConqr? Learn more.