From 8507d7c3961d02e695a85e07d19f2cd9bbc662ba Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
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')

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