commit 4e03a65b7e4da0ede663d419ab986ab3b4a92c10
parent 3a2860175a1e8378dc9f419587c6784c886cc898
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 10 Sep 2025 14:46:19 +0200
commit with codex
Diffstat:
8 files changed, 36 insertions(+), 1 deletion(-)
diff --git a/ancestor b/ancestor
@@ -5,3 +5,5 @@ In a [tree], an ancestor of a [node] is a node on the [path] from the [root] to
Up: [tree]
Aliases: ancestors
+
+See also: [LCA]
diff --git a/lowest_common_ancestor b/lowest_common_ancestor
@@ -0,0 +1,9 @@
+# Lowest common ancestor
+
+The *lowest common ancestor* of two [nodes] in a [tree] is the lowest [node] which is an [ancestor] of both nodes
+
+Up: [tree]
+
+Aliases: LCA
+
+See also: [Lowest_common_ancestor_problem]
diff --git a/lowest_common_ancestor_problem b/lowest_common_ancestor_problem
@@ -0,0 +1,7 @@
+# Lowest common ancestor problem
+
+Given two [nodes] in a [tree], find their [LCA]
+
+A [tree] can be [preprocessed] in [linear_time] to support such queries in [constant_time], cf for instance https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm
+
+Up: [computational_problem], [lowest_common_ancestor]
diff --git a/node b/node
@@ -3,3 +3,5 @@
A [vertex], in a [tree]
Up: [tree]
+
+Aliases: nodes
diff --git a/preprocessing b/preprocessing
@@ -10,4 +10,4 @@ Up: [enumeration_definition]
See also: [delay], [enumeration_phase]
-Aliases: preprocess
+Aliases: preprocess, preprocessed
diff --git a/range_query b/range_query
@@ -3,8 +3,10 @@
Maintain a collection of points and answer queries asking about all the points in a specific range
- [range_sum]: sum the points
+- [RMQ]: with [minimum] or [maximum]
- [range_reporting]: report the points
- [gupta1995further]: range color counting/reporting in [rectangle]
+- [range_query_dynamic]
See also: [skyline], [2d_range_reporting], [range_reporting], [range_tree]
diff --git a/rmq b/rmq
@@ -0,0 +1,11 @@
+# RMQ
+
+https://en.wikipedia.org/wiki/Range_minimum_query
+
+Can be done with [linear_preprocessing] and [constant_time] query in the [RAM_model]
+
+Can be used for [LCA] and for [longest_common_prefix]
+
+Up: [range_query]
+
+Aliases: range min query, range max query, range minimum query, range maximum query, range min, range max
diff --git a/tree b/tree
@@ -23,11 +23,13 @@
- [path]
- [downward_path]
- [tree_labeled]
+- [lowest_common_ancestor]
## [Algorithms] on [trees]
- [tree_traversal]
- [prefix_order], [postfix_order], [infix_order]
+- [lowest_common_ancestor_problem]
## Advanced concepts
