From 8507d7c3961d02e695a85e07d19f2cd9bbc662ba Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Tue, 20 Dec 2022 08:49:56 +0100 Subject: Expand on LCA closure --- presentation/presentation.md | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) (limited to 'presentation/presentation.md') diff --git a/presentation/presentation.md b/presentation/presentation.md index d3ab7be..3004971 100644 --- a/presentation/presentation.md +++ b/presentation/presentation.md @@ -102,7 +102,20 @@ We'll partition the tree such that: * Working bottom-up, we can compute $A$'s state in the root of each part in $O(1)$. -Note: computing the partition takes time $O(m \log{m})$ as it uses a sort. +## LCA Closure Questions + +**Given**: a tree T. + +**Questions**: given $W \subseteq V(T)$, output the LCA closure of $W$. + +Can be solved in $\langle O(n), O(m \log m) \rangle$ (Section 4.1.2). + +## LCA Closure Questions + +* Preprocess for LCA. +* Given $W$, sort it according to in-order numbers. +* Add the LCA's of pairs of subsequent vertices in the sorted list. + ## Types of Parts -- cgit v1.2.3