Fast algorithm for linear context finding I am trying to figure out a quick algorithm which solves the following problem.

For the rest of this question, assume $0\in\mathbb{N}$.

Denote by $\mathbb{R}^\mathbb{N}$ the set of all real sequences and by $\mathbb{N}^\mathbb{N}$ the set of all natural sequences. The algorithm should emulate a function $F:\mathbb{R}^\mathbb{N}\to\mathbb{N}^\mathbb{N}$ which can be defined as follows: given a real sequence $\{x_n\}$, $F(\{x_n\}) = \{y_n\}$, where $y_n$ is the maximum natural number for which both $y_n\le n$ and $x_{n-i} &lt; x_n$ for all $0&lt;i\le y_n$.

The emulation is of the following sense: the algorithm should receive floats, one by one, and for the float $x_n$ return the integer $y_n$. By quick I mean of linear speed. The naive algorithm is $O(n^2)$.

Note: there is a similar (?) algorithm which for a given positive integer $n$, receives a sequence of floats and returns for each the maximal value among the last $n$ received values, which is linear.
You can solve this in $O(n \lg^2 n)$ time.

Build a (balanced) binary tree with $n$ nodes, where the leaves are annotated with the values $x_1,x_2,\dots,x_n$, and $x_i$ is placed on the $i$th leaf from the left.  Annotate each internal node $v$ in the tree with the maximum value over all the leaves in the subtree rooted at $v$.  For instance, the root is annotated with $\max(x_1,x_2,\dots,x_n)$.  The tree and the annotations can be built in $O(n)$ time.

Next, note that, for any $j,k$, a sequence $x_j, x_{j+1}, \dots, x_k$ of consecutive leaves can be covered by some union of $O(\lg n)$ subtrees.  In particular, given any $j,k$, we can compute $\max(x_j,x_{j+1},\dots,x_k)$ in $O(\lg n)$ time, by traversing the tree and using the annotations on the internal nodes at the top of those $O(\lg n)$ subtrees.

Now, to compute $y_k$, we do a binary search to find the largest $j$ such that $\max(x_j,x_{j+1},\dots,x_{k-1})&lt;x_k$ but $\max(x_{j-1},x_j,x_{j+1},\dots,x_{k-1})\ge x_k$.  Each iteration of the binary search takes $O(\lg n)$ time, and the binary search takes at most $O(\lg n)$ iterations, so this allows us to compute each $y_k$ in $O(\lg^2 n)$ time.

Finally, there are $n$ $y$-values that we want to compute, so the total running time is $O(n \lg^2 n)$.

This can be adjusted to work in an incremental/online/streaming fashion, with $O(\lg^2 n)$ running time per value of $x$ received, by tweaking the structure of the binary tree appropriately.



It's possible you might be able to get a slightly better solution by using 2-D range trees, where you store the $n$ points $(i,x_i)$ in the tree (for $i=1,2,\dots,n$).  However, I'm not certain.