From 642690ede9425a31f45e3ac85ad7200273a1896c Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Wed, 5 Mar 2008 14:34:22 +0100
Subject: [PATCH] Bender.

---
 PLAN       | 1 -
 biblio.bib | 2 +-
 ram.tex    | 4 +++-
 3 files changed, 4 insertions(+), 3 deletions(-)

diff --git a/PLAN b/PLAN
index 91ed33e..c75cc05 100644
--- a/PLAN
+++ b/PLAN
@@ -66,7 +66,6 @@ Models:
 - mention in-place radix-sorting?
 - consequences of Q-Heaps: Thorup's undirected SSSP etc.
 - add more context from thorup:aczero, also mention FP operations
-- refs on Cartesian trees
 - update notation.tex
 
 Ranking:
diff --git a/biblio.bib b/biblio.bib
index b638f1b..be57017 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -1,4 +1,4 @@
-@inproceedings{ bender00lca,
+@inproceedings{ bender:lca,
     author = "Michael A. Bender and Martin Farach-Colton",
     title = "The {LCA} Problem Revisited",
     booktitle = "Latin American Theoretical {INformatics}",
diff --git a/ram.tex b/ram.tex
index 7cdf752..ef84a21 100644
--- a/ram.tex
+++ b/ram.tex
@@ -798,7 +798,9 @@ us call this bit~$g_i$. This implies that the values $x_1,\ldots,x_i$
 must lie in the left subtree of the root and $x_{i+1},\ldots,x_n$ in its
 right subtree. Both subtrees can be then constructed recursively.\foot{This
 construction is also known as the \df{cartesian tree} for the sequence
-$g_1,\ldots,g_n$.}
+$g_1,\ldots,g_n$ and it is useful in many other algorithms as it can be
+constructed in $\O(n)$ time. A~nice application on the Lowest Common Ancestor
+and Range Minimum problems has been described by Bender et al.~in \cite{bender:lca}.}
 \qed
 
 \para
-- 
2.39.2