m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
path: root/presentation
diff options
context:
space:
mode:
Diffstat (limited to 'presentation')
-rw-r--r--presentation/presentation.md15
1 files changed, 14 insertions, 1 deletions
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