diff options
| author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2022-12-20 08:49:56 +0100 |
|---|---|---|
| committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2022-12-20 08:49:56 +0100 |
| commit | 8507d7c3961d02e695a85e07d19f2cd9bbc662ba (patch) | |
| tree | d4d3ff7b5ce61e8970049be4eaecb2d25369902a | |
| parent | 9436701bc08ed12318a66ea94d209a5a9b23648f (diff) | |
Expand on LCA closure
| -rw-r--r-- | presentation/presentation.md | 15 |
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 |