---
abstract: |
    We study multi-finger binary search trees (BSTs), a far-reaching extension of the classical BST model, with connections to the well-studied $k$-server problem. Finger search is a popular technique for speeding up BST operations when a query sequence has *locality of reference*. BSTs with *multiple* fingers can exploit more general regularities in the input. In this paper we consider the cost of serving a sequence of queries in an optimal (offline) BST with $k$ fingers, a powerful benchmark against which other algorithms can be measured.

    We show that the $k$-finger optimum can be matched by a standard dynamic BST (having a single root-finger) with an $O(\log{k})$ factor overhead. This result is tight for all $k$, improving the $O(k)$ factor implicit in earlier work. Furthermore, we describe new *online* BSTs that match this bound up to a $(\log{k})^{O(1)}$ factor. Previously only the “one-finger” special case was known to hold for an online BST (Iacono, Langerman, 2016; Cole et al., 2000). Splay trees, assuming their conjectured optimality (Sleator and Tarjan, 1983), would have to match our bounds for all $k$.

    Our online algorithms are randomized and combine techniques developed for the $k$-server problem with a multiplicative-weights scheme for learning tree metrics. To our knowledge, this is the first time when tools developed for the $k$-server problem are used in BSTs. As an application of our $k$-finger results, we show that BSTs can efficiently serve queries that are *close to some recently accessed item*. This is a (restricted) form of the *unified property* (Iacono, 2001) that was previously not known to hold for any BST algorithm, online or offline.
author:
- Parinya Chalermsook
- Mayank Goswami
- László Kozma
- Kurt Mehlhorn
- Thatchaphol Saranurak
bibliography:
- 'article.bib'
title: 'Multi-finger binary search trees'
---

Introduction
============

The binary search tree (BST) is the canonical comparison-based implementation of the dictionary data type for maintaining ordered sets. Dynamic BSTs can be re-arranged after every access via rotations and pointer moves starting from the root. Various ingenious techniques have been developed for dynamically maintaining balanced BSTs, supporting search, insert, delete, and other operations in time $O(\log{n})$, where $n$ is the size of the dictionary (see e.g. [@Knuth3 §6.2.2], [@Mehlhorn84 §5]).

In several applications where the access sequence has strong *locality of reference*, the worst-case bound is too pessimistic (e.g. in list merging, adaptive sorting, or in various geometric problems). A classical technique for exploiting locality is *finger search*. In finger search trees, the cost of an access is typically $O(\log{d})$,[^1] where $d$ is the difference in rank between the accessed item and a *finger* ($d$ may be much smaller than $n$). The finger indicates the starting point of the search, and is either given by the user, or (more typically) it points to the previously accessed item. Several special purpose tree-like data structures have been designed to support finger search.[^2]

In 1983, Sleator and Tarjan [@ST85] introduced Splay trees, a particularly simple and elegant “self-adjusting” BST algorithm. In 2000, Cole et al. [@finger1; @finger2] showed that Splay matches (asymptotically) the efficiency of finger search, called in this context the *dynamic finger* property. This is remarkable, since Splay uses no explicit fingers; every search starts from the root. The result shows the versatility of the BST model, and has been seen as a major (and highly nontrivial) step towards “dynamic optimality”, the conjecture of Sleator and Tarjan that Splay trees are constant-competitive.

BSTs can also adapt to other kinds of locality. The *working set* property [@ST85] requires the amortized cost of accessing $x$ to be $O(\log{t})$, where $t$ is the number of distinct items accessed since the last access of $x$. Whereas dynamic finger captures proximity in keyspace, the working set property captures proximity *in time*. In 2001, Iacono [@IaconoUnified] proposed a *unified* property that generalizes both kinds of proximity. Informally, a data structure with the unified property is efficient when accessing an item that is *close to some recently accessed item*. [It is not known whether any BST data structure has the unified property.]{}

Recently, Iacono and Langerman [@LI16] studied the *lazy finger* property (Bose et al. [@BoseDIL14]), and showed that an online algorithm called Greedy BST[^3] satisfies it. The lazy finger property requires the amortized cost of accessing $x$ to be $O(d)$, where $d$ is the distance (number of edges) from the previously accessed item to $x$ in the best *static reference tree*. This property is stronger than the dynamic finger property [@BoseDIL14], and it is not known to hold for Splay.

In this paper we study a generalization of the lazy finger property; instead of a single finger stationed at the previously accessed item, we allow $k$ fingers to be moved around arbitrarily. An access is performed by moving any of the fingers to the requested item. Cost is proportional to the *total* distance traveled by the fingers. We assume that the fingers move according to an optimal strategy, in an optimally chosen static tree, with a priori knowledge of the entire access sequence. The cost of this optimal *offline* execution with $k$ fingers is an intrinsic measure of complexity of a query sequence, and at the same time a benchmark that algorithms in the classical model can attempt to match. Parameter $k$ describes the strength of the bound: the case $k=1$ is the lazy finger, at the other extreme, at $k=n$, each item may have its own finger, and all accesses are essentially free.

Our main result is a family of new *online*[^4] dynamic BST algorithms (in the standard model, where every access starts at the root), matching the $k$-finger optimum on sufficiently long sequences, up to an overhead factor with moderate dependence on $k$ and no dependence on the dictionary size or on the number of accesses in the sequence.

Our online BST combines three distinct techniques: (1) an offline, one-finger BST simulation of a multi-finger execution (the technique is a refinement of an earlier construction [@CombineBST]), (2) online $k$-server algorithms that can simulate the offline optimal multi-finger strategy, and (3) a multiplicative-weights scheme for learning a tree metric in an online fashion.

The fact that “vanilla” BSTs can, with a low overhead, simulate a much more powerful computational model further indicates the strength and versatility of the BST model. As an application, we show that our online BST algorithms satisfy a restricted form of the *unified property*; previously no (online or offline) BST was known to satisfy such a property.

If there is a constant-competitive BST algorithm, then it must match our $k$-finger bounds. The two most promising candidates, Splay and Greedy BST (see e.g. [@in_pursuit]) were only shown (with considerable difficulty) to satisfy variants of the one-finger, i.e. lazy finger property. To obtain our online BSTs competitive for other values of $k$, we combine sophisticated tools developed for other online problems, as well as our refinement of a previous (highly nontrivial) construction for simulating multiple fingers. These facts together may hint at the formidable difficulty (more pessimistically: the low likelihood) of attaining dynamic optimality by simple and natural BST algorithms such as Splay or Greedy.

##### BST and finger models. Main results. {#bst-and-finger-models.-main-results. .unnumbered}

Now, we introduce the formal statements of our results. In the dynamic BST model a sequence of keys [is]{} accessed in a binary search tree (BST), and after each access, the tree can be reconfigured via a sequence of rotations and pointer moves starting from the root. (There exist several alternative but essentially equivalent models, see [@Wilber; @DHIKP09].) Denote the space of keys (or elements) by $[n]$. For a sequence $X = (x_1,\ldots, x_m) \in [n]^m$, denote by ${\sf OPT}(X)$ the cost of the optimal offline BST for accessing $X$.[^5] Arguably the most important question in the BST model is the dynamic optimality conjecture, i.e. the existence of an online BST whose cost is $O({\mbox{\sf OPT}}(X))$ for every $X$.

A BST [*optimality property*]{} is an inequality between ${\sf OPT}(X)$ and some function $f(X)$, that holds in the BST model. (If ${\sf OPT}(X) \leq f(X)$ for all $X$ is a BST optimality property, then every $O(1)$-competitive algorithm must cost at most $O(f(X))$.)

Several natural BST properties have been suggested over the last few decades. For instance, the *static finger* property [@ST85] states ${\mbox{\sf OPT}}(X) =O({\mbox{\sf SF}}(X))$, for ${\mbox{\sf SF}}(X) = \sum_t \log |x_t - j|$, where $j \in [n]$ is a fixed element (finger). The *static optimality* property [@ST85] is ${\mbox{\sf OPT}}(X) =O({\mbox{\sf SO}}(X))$, where ${\mbox{\sf SO}}(X) = \min_R \sum_{i} d_R(x_i)$. Here $R$ is a *static* BST, and $d_R(x)$ is the depth of $x$ in $R$.

For the *dynamic finger* property [@ST85], ${\mbox{\sf DF}}(X) =\sum_t \log |x_t - x_{t+1}|$, and for *working set* [@ST85], ${\mbox{\sf WS}}(X) = \sum_t \log \rho_t(x_t)$, where $\rho_t(a)$ is the number of distinct keys accessed between time $t$ and the last time at which $a$ was accessed (all keys assumed accessed at time zero).

In 2001, Iacono [@IaconoUnified] initiated the study of a property that would “unify” the latter two notions of efficiency and exhibited a data structure (not a BST) achieving this property. This *unified bound* is defined as ${\mbox{\sf UB}}(X) = \sum_{t} \min_{t' < t} \log (|x_t - x_{t'}| + \rho_{t}(x_{t'}))$. Dynamic finger and working set are in general, not comparable. On the other hand, ${\mbox{\sf UB}}(X) \leq {\mbox{\sf DF}}(X)$, and ${\mbox{\sf UB}}(X) \leq {\mbox{\sf WS}}(X)$ clearly hold, justifying the name of the unified bound.

Despite several attempts, the question whether the unified bound is a valid BST property remains unclear; it was shown in [@DerryberryS09] that ${\mbox{\sf OPT}}(X) = O({\mbox{\sf UB}}(X) +m\log \log n)$, and in [@unified; @IaconoUnified] that the unified bound is valid in some other (non-BST) models[^6]. We show that a unified bound with “bounded time-window” holds in the BST model:

\[thm: weak UB\] For every integer $\ell \geq 1$, every sequence $X$ and some fixed function $\beta(\cdot)$, $${\mbox{\sf OPT}}(X) \leq \beta(\ell) \cdot {\mbox{\sf UB}}^{\ell}, \mbox{~~where~~~~} {\mbox{\sf UB}}^{\ell} = \sum_t \min_{t'\in [t-\ell,t)} \log \big(|x_t - x_{t'}| + \rho_t(x_{t'})\big) .$$

Observe that ${\mbox{\sf UB}}(X) = {\mbox{\sf UB}}^{m}(X) \leq \cdots \leq {\mbox{\sf UB}}^1(X) = {\mbox{\sf DF}}(X)$. Prior to our work it was not known whether the theorem holds when $\ell=2$, i.e. no known BST property subsumes this property even when $\ell =2$. Thus, Theorem \[thm: weak UB\] establishes the first BST property that combines the efficiencies of time- and keyspace-proximity without an additive term.[^7]

Recently Bose et al. [@BoseDIL14] introduced the *lazy finger* property, ${\mbox{\sf LF}}(X) = \min_R \sum_{i} d_R(x_i,x_{i+1})$. Here distance is measured in a static reference BST $R$, optimally chosen for the entire sequence. The lazy finger bound can be visualized as follows: accesses are performed in the reference tree by moving a unique finger from the previously accessed item to the requested item. The lazy finger property is rather strong: Bose et al. show that it implies the dynamic finger and static optimality properties, which in turn imply static finger. Our main tool in proving Theorem \[thm: weak UB\] is a generalization of the lazy finger property allowing multiple fingers. The model is motivated by the famous $k$-server problem. For an input sequence $X \in [n]^m$ and a static BST $R$ with nodes associated with the keys in $[n]$, we have $k$ servers located initially at arbitrary nodes in $R$. At time $t=1,\ldots, m$, the request $x_t$ arrives, and we move a server of our choice to the node of $R$ that stores $x_t$. The cost for serving a sequence $X$ is equal to the total movement in $R$ to serve the sequence $X$.

Denote by ${\mbox{\sf F}}^{k}_R(X)$ the cost of the optimal (offline) strategy that serves sequence $X$ in $R$ with $k$ servers, minimized over all possible initial server locations. Let ${\mbox{\sf F}}^{k}(X) = \min_R {\mbox{\sf F}}^{k}_R(X)$. We call ${\mbox{\sf F}}^{k}(X)$ the [*$k$-finger cost*]{} of $X$. We remark that the value of ${\mbox{\sf F}}^{k}_R(X)$ is polynomial-time computable for each $R$, $k\in {\mathbb N}$, and $X \in [n]^m$ by dynamic programming. Clearly, ${\mbox{\sf F}}^{1}(X) \geq {\mbox{\sf F}}^{2}(X) \geq \cdots \geq {\mbox{\sf F}}^{n}(X)$ holds for all $X$.

We first show that one can simulate any $k$-finger strategy in the BST model, in a near-optimal manner. In particular, we prove the following tight result.

\[thm: LF simulation\] ${\mbox{\sf OPT}}(X) \leq O(\log k) \cdot {\mbox{\sf F}}^{k}(X)$.

The proof of Theorem \[thm: LF simulation\] is a refinement of an earlier argument [@CombineBST], improving the overhead factor from $O(k)$ to $O(\log{k})$. The logarithmic dependence on $k$ is, in general, the best possible. To see this, consider a sequence $S$ of length $m$, over $k$ distinct items with average cost $\Omega{(\log{k})}$ (e.g. a random sequence from $[k]^m$ does the job). While ${\mbox{\sf OPT}}{(S)} = \Theta(m\log{k})$, clearly ${\mbox{\sf F}}^{k}(X)=O(m)$, as each of the $k$ items can be served with its own private finger.

In the definition of ${\mbox{\sf F}}^k(X)$ we assume a *static* reference tree $R$ for the $k$-finger execution. The offline BST simulation in the proof of Theorem \[thm: LF simulation\] works in fact (with the same overhead) even if $R$ is *dynamic*, i.e. if the multi-finger adversary can perform rotations at any of the fingers. In this case, however, the $k$-finger bound is too strong to be useful; already the $k=1$ case captures the dynamic BST optimum. Our next result is the online counterpart of Theorem \[thm: LF simulation\]. In this case, the restriction that $R$ is static is essential.

\[thm: online simulation\] There exists an online randomized BST algorithm whose cost for serving $X \in [n]^m$, is $O\bigl((\log k)^7\bigr) \cdot {\mbox{\sf F}}^{k}(X) + \rho(n)$, for some fixed function $\rho(\cdot)$.

The result can be interpreted as follows. On sufficiently long access sequences, there is an online BST algorithm (in fact, a family of them) competitive with the $k$-finger bound, up to an overhead factor with moderate dependence on $k$. The randomized algorithm (as is standard in the online setting) assumes an oblivious adversary that does not know in advance the outcomes of the algorithm’s random coin-flips. The use of randomness seems essential to our approach. We propose as intriguing open questions to find a deterministic online BST with comparable guarantees and to narrow the gap between the online and offline results.

Due to its substantial amount of computation (outside the BST model), our online algorithm is of theoretical interest only. Nonetheless, the connection with the $k$-server problem allows us to “import” several techniques to the BST problem; some of these, such as the *double coverage* heuristic for $k$-server [@chrobak] are remarkably simple and may find their way to practical BST algorithms.

The strength of the $k$-finger model lies in the $k$-server abstraction. In order to establish a BST property of the form ${\mbox{\sf OPT}}(X) \leq \beta(\ell) \cdot O(g(X))$, it is now sufficient to prove ${\mbox{\sf F}}^{\ell}(X) \leq \left(\beta(\ell)/\log{\ell}\right) \cdot O(g(X))$. In other words, our technique reduces the task of bounding the cost in the BST model to designing $k$-server strategies, which typically admits much cleaner combinatorial arguments. We illustrate this approach by showing that the unified property with a fixed time-window holds in the BST model.

\[thm: strategy for min-dist\] For some fixed functions $\alpha(\cdot),\gamma(\cdot)$, we have:  ${\mbox{\sf F}}^{\alpha(\ell)}(X) \leq \gamma(\ell) \cdot {\mbox{\sf UB}}^{\ell} $.

Theorems \[thm: strategy for min-dist\] and \[thm: LF simulation\] together imply Theorem \[thm: weak UB\]. Moreover, Theorem \[thm: online simulation\] implies that the property holds for *online* BST algorithms (we later specify the involved functions). The $k$-finger approach can be used to show further BST properties. For example, we connect *decomposability* (refer to 4 for definitions) and finger properties by showing that even one finger is enough to obtain the *traversal* property in significantly generalized form.

\[thm:decomp\] Let $X$ be a $d$-decomposable sequence. Then ${\mbox{\sf F}}^{1}(X) = O(\log d) \cdot |X| $.

As a corollary, using the recent result by Iacono and Langermann [@LI16], we resolve an open problem in [@FOCS15], showing that Greedy costs at most $O(\log d)\cdot |X|$ on every $d$-decomposable sequence, matching the lower bound in [@FOCS15].[^8]

In another direction, we connect multiple fingers and generalized monotone sequences. In [@FOCS15], we showed that ${\mbox{\sf OPT}}(X) \leq |X|\cdot 2^{O(d^2)}$ on every $d$-monotone sequence $X$; a sequence is $d$-monotone if it can be decomposed into $d$ increasing or $d$ decreasing sequences. Using the $k$-finger technique, we show the stronger BST property ${\mbox{\sf OPT}}(X) \leq O(d \log d) \cdot |X|$.

Concerning simple and natural BST algorithms (Splay and Greedy), we give evidence that the strongest results in the literature may still be far from settling the dynamic optimality conjecture. To this end, we describe a class of sequences for which increasing the number of fingers by one can create an $\Omega(\log n)$ gap. More precisely, we show the following:

\[thm:hierarchyx\] For every integer $k$, there is a sequence $S_k$ such that ${\mbox{\sf F}}^{k-1}(S_k) = \Omega(\frac{n}{k} \log (n/k))$ but ${\mbox{\sf F}}^{k}(S_k) = O(n)$.

Theorem \[thm:hierarchyx\] shows that the multi-finger bounds form a fine-grained hierarchy. For small $k$, our online algorithm (Theorem \[thm: online simulation\]) can match these bounds (up to a constant factor). However, any online BST (such as Splay or Greedy) must also match the dependence of $O(\log k)$ in the upper bound of $O(\log k) \cdot F^{k}(X)$, in order to be constant-competitive.

##### Techniques. The $k$-server problem. {#techniques.-the-k-server-problem. .unnumbered}

The $k$-server problem, introduced by Manasse, McGeoch, and Sleator [@Manasse] in 1988 is a central problem in online algorithms: Is there an online deterministic strategy for serving a sequence of requests by moving $k$ servers around, with a total movement cost at most $k$ times the optimal offline strategy? The question in its original form, for arbitrary metric spaces, remains open. Nonetheless, the problem has inspired a wealth of results and a rich set of techniques, many of which have found applications outside the $k$-server problem. A full survey is out of our scope, we refer instead to some prominent results [@Fiat; @Koutsoupias; @Seiden; @Raghavan; @Bartal; @Bansal], and the surveys [@Borodin §10, §11], [@kserver_survey]. Most relevantly for us, Chrobak and Larmore [@chrobak] gave in 1991, an intuitive, deterministic, $k$-competitive algorithm for *tree metrics*, and the very recently announced breakthrough of Lee [@Lee], building on Bubeck et al. [@Bubeck], gives an $O\bigl((\log{k})^6\bigr)$-competitive randomized algorithm for arbitrary metrics.

Our online BST algorithm relies on an online $k$-server in an almost black box fashion (the metric space underlying the $k$-server instance is induced by a static reference BST). Thus, improvements for $k$-server would directly yield improvements in our bounds. Despite the depth and generality of $k$-server (e.g. it also models the caching/paging problem), to our knowledge it has previously not been related to the BST problem.[^9]

It is known that in an arbitrary metric space with at least $k+1$ points, no deterministic online algorithm may have a competitive ratio better than $k$. In the randomized case the lower bound $\Omega(\log{k}/\log{\log{k}})$ holds, see e.g. [@kserver_survey]. (The lower bounds thus apply for a metric induced by a BST, for all $k<n$.) These results imply a remarkable separation between the $k$-server and BST problems. Dynamic optimality would require, by Theorem \[thm: LF simulation\], a BST cost of $O(\log{k})\cdot {\mbox{\sf F}}^k$. To match this, an online BST may not implicitly perform a deterministic $k$-server execution, since, in that case its overhead would have to be $\Omega{(k)}$. This indicates that improving Theorem \[thm: online simulation\] will likely require tools significantly different from $k$-server, which is surprising, given the similarity of the two formulations.

Our online BST learns the metric induced by the optimal reference tree using a multiplicative weights update (MWU) scheme. The technique has a rich history, and a recent emergence as a powerful algorithmic tool (we refer to the survey of Arora, Hazan, and Kale [@AroraSurvey]). MWU or closely related techniques have been used previously in data structures (including for BST-related questions), see e.g. [@Blum; @BlumBurch; @in_pursuit; @Kalai]. Specifically, Iacono [@in_pursuit] obtains, using MWU, an online BST that is constant-competitive on sufficiently long sequences, *if any online BST is constant-competitive*. As we relate online BSTs with an offline strategy, the results are not directly comparable.

##### Further open questions and structure of the paper. {#further-open-questions-and-structure-of-the-paper. .unnumbered}

The main open question raised by our work is whether natural algorithms such as Splay or Greedy match the properties of our new BST algorithms. (This must be the case, if Splay and Greedy are, as conjectured, $O(1)$-competitive). We suggest the following easier questions. Do Splay or Greedy satisfy the unified bound with a time-window of $2$ steps? Does Splay satisfy the lazy finger or the $2$-monotone bounds? Does Greedy satisfy the $2$-finger bound?

Except for Theorems \[thm: LF simulation\] and \[thm:decomp\], the factors in our results are not known to be tight. Improving them may reveal new insight about the power and limitations of the BST model.

In §\[sec2\] we describe our offline BST simulation. In §\[sec3\] we describe our new family of online algorithms. In §\[sec4\] we prove the main applications and further observations.

Offline simulation of multi-finger BSTs (Theorem \[thm: LF simulation\]) {#sec2}
========================================================================

Let $k \in {\mathbb N}$ , let $T$ be a BST on $[n]$, and let $X = (x_1,\dots,x_m) \in [n]^m$ be an access sequence. A $k$-*finger strategy* consists of a sequence $\vec{f} \in [k]^m$ where $f_t \in [k]$ specifies the finger that serves access $x_t$. Let $\vec{\ell} \in [n]^k$ be the [*initial vector*]{}, where $\ell_i \in [n]$ gives the initial location of finger $i$. The cost of strategy $(\vec{f},\vec{\ell})$ is ${\mbox{\sf F}}^{k}_{T,\vec{f}, \vec{\ell}}(X) = \sum_{t=1}^m (1+d_T(x_t, x_{\sigma(f_t,t)}))$ where $\sigma(i,t) = \max\{j < t \mid f_j = i\}$ is the location of finger $i$ before time $t$, and $\sigma(i,1) = \ell_i$. Let ${\mbox{\sf F}}^{k}_T(X) = \min_{\vec{f}, \vec{\ell}} {\mbox{\sf F}}^{k}_{T,\vec{f}, \vec{\ell}} (X)$. In other words, for a fixed BST $T$ on keyset $[n]$, ${\mbox{\sf F}}^{k}_T(X)$ is the *$k$-server* optimum for serving $X$ in the metric space of the tree $T$. (Note that the tree is unweighted, and the distance $d_T(\cdot,\cdot)$ counts the number of edges between two nodes in $T$.) We define ${\mbox{\sf F}}^{k}(X) = \min_T {\mbox{\sf F}}^{k}_{T}(X)$. It is clear form the definition that ${\mbox{\sf F}}^{1}(X) \geq {\mbox{\sf F}}^{2}(X) \geq \cdots \geq {\mbox{\sf F}}^{n}(X) = m$ for all $X$.

Observe that we implicitly assume that during every access at most one server moves. In addition, we may assume that if some server is already placed at the requested node, then no movement happens. Algorithms with these two restrictions are called *lazy*. As argued in the $k$-server literature (see e.g. [@kserver_survey]), non-lazy server movements can always be postponed to a later time, keeping track of the “virtual” locations of servers. In other words, every $k$-server algorithm can be simulated by a lazy algorithm, without additional cost. We therefore assume throughout the paper that $k$-server/$k$-finger executions are lazy.

Consider some (lazy) $k$-finger execution $(\vec{f},\vec{\ell})$ in tree $T$, for access sequence $X$. We can view $\vec{f}$ as an explicit sequence of elementary steps ${\ensuremath{\mathcal S}}= {\ensuremath{\mathcal S}}^k_{T, \vec{f}, \vec{\ell}}$, where in each step we move one of the fingers to its parent or to one of its children in $T$. We further allow ${\ensuremath{\mathcal S}}$ to contain rotations at a finger in $T$ (although $k$-finger strategies as described above do not generate rotations). The position of a finger is maintained during a rotation.

We show how ${\ensuremath{\mathcal S}}$ can be simulated in a standard dynamic BST. If in ${\ensuremath{\mathcal S}}$ a finger visits a node, then the (single) pointer in the BST also visits the corresponding node, therefore all accesses are correctly served in the BST. Every elementary step in ${\ensuremath{\mathcal S}}$ is mapped to (amortized) $O(\log{k})$ elementary steps (pointer moves and rotations) in the BST. This immediately implies Theorem \[thm: LF simulation\], since, if we can simulate an arbitrary $k$-finger execution, then indeed we can simulate the optimal $k$-finger execution on the best static tree. Assuming that the intial conditions $T$ and $\vec{\ell}$ are known, the steps of ${\ensuremath{\mathcal S}}$ are simulated one-by-one, without any lookahead. Thus, insofar as the $k$-finger execution is *online*, the BST execution is also online (this fact is used in §\[sec3\]).

Let us describe simulation by a standard BST $T'$ of a $k$-finger execution ${\ensuremath{\mathcal S}}$ in a BST $T$. The construction is a refinement of the one given by Demaine et al. [@CombineBST], see also [@persistent_tries]. (We improve the overhead factor from $O(k)$ to $O(\log{k})$.) The main ingredients are: (1) Making sure that each item with a finger on it in $T$ has depth at most $O(\log k)$ in $T'$. (In [@CombineBST], each finger may have depth up to $O(k)$ in $T'$.) (2) Implementing a deque data structure within $T'$ so that each finger in $T$ can move to any of its neighbors, or perform a rotation, with cost $O(\log k)$ amortized. (In [@CombineBST], this cost is $O(1)$ amortized.)

Given these ingredients, to move a finger $f$ to its neighbor $x$ in $T$, we can simply access $f$ from the root of $T'$ in $O(\log k)$ steps, and then move $f$ to $x$ in $T'$ in $O(\log{k})$ amortized steps, with a similar approach for a rotation at $f$. Hence, the overhead factor is $O(\log k)$. We sketch the main technical ideas, postponing the details to Appendix \[sec:simulation lazy fingers\].

Consider the tree $S$ induced by the current fingers and the paths connecting them in $T$. The tree $S$ consists of finger-nodes and non-finger nodes of degree 3 (both types of nodes are called *pseudo-fingers*), and paths of non-finger nodes of degree 2 connecting pseudo-fingers with each other, called *tendons*. Tendons can be compressed into a BST structure that allows their traversal between the two endpoints in $O(1)$ steps.

We maintain $S$ as a root-containing subtree of our BST $T'$, called the *hand*. Due to the compression of the tendons, the relevant part of $S$ has size $O(k)$. The description so far, including the terminology, is identical to the one in [@CombineBST §2]. Our construction differs in the fact that it maintains the hand, i.e. the compressed representation of $S$ as a *balanced* BST. This guarantees the reachability of fingers in $O(\log{k})$ instead of $O(k)$ steps, i.e. property (1).

When a finger in $T$ moves or performs a rotation, the designation of some (pseudo)finger, or tendon nodes may change. Such changes can be viewed as the insertion or deletion of items in the tendons. As these operations happen only at certain places within the tendons, they can be implemented efficiently. We implement tendons with the same BST-based *deque* as [@CombineBST]. The construction appears to be folklore, we describe it in Appendix \[deque\_proof\] for completeness.

We depart again from [@CombineBST], as the operation affecting the (pseudo)finger and tendon nodes can trigger a re-balancing of the hand, which may again require $O(\log{k})$ operations to fix, i.e. property (2). Any efficient balancing strategy (e.g. red-black tree) may be used.

Online simulation of multi-finger BSTs (Theorem \[thm: online simulation\]) {#sec3}
===========================================================================

Consider the optimal (offline) $k$-finger execution $\vec{f}$ for access sequence $X \in [n]^m$, with static reference tree $T$ and initial finger-placement $\vec{\ell}$. We wish to simulate it by a dynamic *online* BST. The construction proceeds in two stages: (1) A simulation of $\vec{f}$ by a sequence ${\ensuremath{\mathcal S}}$ of steps that describe finger-movements and rotations-at-fingers, starting from an arbitrary BST $T_0$ and arbitrary finger locations $\vec{\ell}_0$. The sequence ${\ensuremath{\mathcal S}}$ is *online*, i.e. it is constructed without knowledge of the optimal initial state $T$,$\vec{\ell}$, and it correctly serves the sequence $X$, as its elements are revealed one-by-one. (2) A step-by-step simulation of ${\ensuremath{\mathcal S}}$ by a standard BST algorithm using the result of §\[sec2\]. Since ${\ensuremath{\mathcal S}}$ is online, the BST algorithm is also online.

As before, we denote by ${\mbox{\sf F}}^k(X) = {\mbox{\sf F}}^{k}_{T,\vec{f}, \vec{\ell}}(X)$ the cost of the optimal offline execution. Observe that this is exactly the $k$-server optimum with the tree metric defined by $T$ and initial configuration of servers $\vec{\ell}$. If $T$ and $\vec{\ell}$ were known, we could conclude part (1) by running an arbitrary *online* $k$-server algorithm defined on tree metrics.

To this end, we mention two online $k$-server algorithms, the deterministic “double coverage” algorithm of Chrobak and Larmore [@chrobak] (Algorithm A) and the very recently announced randomized algorithm of Lee [@Lee; @Bubeck] (Algorithm B). It is known that the cost of Algorithms A, resp. B is at most $k$-times, resp. $O((\log{k})^{6})$ times ${\mbox{\sf F}}^k$. We only describe Algorithm A, as it is particularly intuitive. To obtain the claimed result, we need the much more complex Algorithm B. (By using Algorithm A we get an overall factor $O(k \log{k})$.)

During the execution of Algorithm A, given a current access request $x_t$, call those servers (fingers) *active*, whose path to $x_t$ in $T$ does not contain another server. If several servers are in the same location, one of them is chosen arbitrarily to be active. Algorithm A serves $x_t$ as follows: as long as there is no server on $x_t$, move all active servers one step closer to $x_t$. Observe that as servers move, some of them may become inactive. Algorithm A (as described) may need to move multiple servers during one access. It can, however, easily be transformed into a lazy algorithm, as discussed in §\[sec2\].

Remains the issue that the optimal initial $T$ and $\vec{\ell}$ are not known. Let $B_1, \dots, B_N$ be instances of an online $k$-server algorithm (in our case Algorithm B), one for each combination of initial tree $T$ and initial server-placement $\vec{\ell}$. Note that $N = O(4^n \cdot {n^k})$. Let ${{\mathcal{M}}}$ be a “meta-algorithm” that simulates all $B_j$’s for $j=1,\dots,N$, competitive on sufficiently long input with the best $B_j$. Algorithm ${{\mathcal{M}}}$ processes $X$ in epochs of length $M = n \log n$, executing in the $i$-th epoch, for $i=1,\dots,\lceil m/M \rceil$, some $B_{\tau(i)}$ according to a (randomized) choice $\tau(i)$.

Suppose that $\vec{\ell}^*$ and $T^*$ describe the state of $B_{\tau(i)}$ chosen by ${{\mathcal{M}}}$ at the beginning of the $i$-th epoch. To switch to the state $\vec{\ell}^*$, $T^*$, ${{\mathcal{M}}}$ takes $O(n \log{n})$ elementary steps: (1) rotate the current tree to a *balanced* tree using any of the fingers ($O(n)$ steps), (2) move all fingers to their location in $\vec{\ell}^*$ ($k$ times $O(\log{n})$ steps), (3) use an arbitrary finger $f$ to rotate the tree to $T^*$ ($O(n)$ steps), (4) move $f$ back to its location in $\vec{\ell}^*$ ($O(n)$ steps). [Since $M = n \log n$]{}, the cost of switching can be amortized over the epoch.

The choice of $B_{\tau(i)}$ for epoch $i$ is done according to the multiplicative-weights (MW) technique [@AroraSurvey], based on the past performance of the various algorithms. Our *experts* are the online executions $B_1, \dots, B_N$, our $i$-th *event* is the portion of $X$ revealed in the $i$-th epoch, the *loss* of the $j$-th expert for the $i$-th event is the *cost* of $B_j$ in the $i$-th epoch. Let $C_{max}$ denote the maximum possible loss of an expert for an event (we may assume $C_{max} \leq n \cdot M$).

It follows from the standard MW-bounds [@AroraSurvey Thm. 2.1], that for an arbitrary $\varepsilon \in (0,1)$, the cost of ${{\mathcal{M}}}$ on $X$ is at most [$\min_j (1+\varepsilon)\mathcal{C}_j + \displaystyle\frac{C_{max} \cdot \ln{N}}{\varepsilon}$, where $\mathcal{C}_j$ is the cost of expert $B_j$ for the entire $X$; in particular, $B_j$ may correspond to the optimal offline choice $\vec{\ell}$, $T$, in which case $\mathcal{C}_j=O((\log{k})^6) \cdot {\mbox{\sf F}}^k(X)$.]{}

Thus, for e.g. $\varepsilon = 1/2$, we obtain that the cost of ${{\mathcal{M}}}$ on $X$ is at most $O((\log{k})^6) \cdot {\mbox{\sf F}}^k(X) + O(n^3 \log^2{n} )$. The output of ${{\mathcal{M}}}$ is an *online* sequence ${\ensuremath{\mathcal S}}_\mathcal{M}$ of rotations and finger moves, starting from an arbitrary initial state $T_0$ and $\vec{\ell}_0$. Note that while ${{\mathcal{M}}}$ needs to evaluate the costs and current states for all experts in all epochs (an extraordinary amount of computation), only one of the experts interacts with the tree at any time. Thus, ${\ensuremath{\mathcal S}}_\mathcal{M}$ is a standard sequence of steps which can be simulated by a standard BST algorithm according to Theorem \[thm: LF simulation\], at the cost of a further $O(\log{k})$ factor. This concludes the proof of Theorem \[thm: online simulation\].

Applications of the multi-finger property {#sec4}
=========================================

In this section we show that every BST algorithm that satisfies the $k$-finger property also satisfies the unified bound with fixed time-window (Application 1), is efficient on decomposable sequences (Application 2), and on generalized monotone sequences (Application 3).

##### Application 1. Combined space-time sensitivity (Theorem \[thm: strategy for min-dist\]). {#application-1.-combined-space-time-sensitivity-theoremthm-strategy-for-min-dist. .unnumbered}

Recall the definition of ${\mbox{\sf UB}}^{\ell}$ in Theorem \[thm: weak UB\] for a sequence $X=(x_{1},\dots, x_{m}) \in [n]^m$. We connect this quantity with the $k$-finger cost, from which Theorem \[thm: strategy for min-dist\] immediately follows.

For every $\ell$, $F^{(\ell!)}(X)=O(\ell!)\cdot\kmin(X)$.\[thm:LF less than kmin\]

Since we are only concerned with the case when $\ell$ is constant, we may drop the term $\rho_t(x_{t'})$ in the definition of ${\mbox{\sf UB}}^{\ell}$ (whose value is always between $1$ and $\ell$).

We prove Theorem \[thm:LF less than kmin\] via another bound in which distances are measured in a static reference BST:$
\displaystyle\kmintree_{T}(X)=\sum_{i=1}^{m}\min_{i-\ell\le j<i}\left\{d_{T}(x_{i},x_{j}) + 1\right\}$. [^10]

$\min_{T}\kmintree_{T}(X)=O(\kmin(X))$.\[thm:distree to dist\]

By [@SeidelA96 Thm. 4.7], there is a randomized BST $\tilde{T}$ such that the expected distance between elements $i$ and $j$ is $E[d_{\tilde{T}}(i,j)]=\Theta(\log|i-j|)$. Therefore, $$\begin{aligned}
\min_{T}\kmintree_{T}(X)  \le  E[\sum_{i=1}^{m}\min_{i-\ell\le j<i}\{d_{\tilde{T}}(x_{i},x_{j})+1\}]
 =  \sum_{i=1}^{m}E[\min_{i-\ell\le j<i}\{d_{\tilde{T}}(x_{i},x_{j})+1\}]\\
 \quad \le  \sum_{i=1}^{m}\min_{i-\ell\le j<i}\{E[d_{\tilde{T}}(x_{i},x_{j})+1]\}
 =  \sum_{i=1}^{m}\min_{i-\ell\le j<i}\{O(\log|x_{i}-x_{j}|)\}
 =  O(\kmin(X)). \quad \quad \qedhere\end{aligned}$$

It is now sufficient to show that ${\mbox{\sf F}}^{(\ell!)}_{T}(X)=O(\ell!)\cdot\kmintree_{T}(X)$, for all $X$ and $T$, i.e. to describe an $(\ell !)$-finger strategy in $T$ for serving $X$ with the given cost.

At a high level, our strategy is the following: (1) Define a *virtual tree* ${{\mathcal T}}(X)$ whose nodes are the *requests* $x_i$ for $i=1,\dots,m$. The virtual tree captures the *proximities* between the requests, with each $x_i$ having as parent the *nearest* request $x_j$ within a fixed time-window before time $i$. Edges in ${{\mathcal T}}(X)$ are given as weights the distances between requests in $T$. Note that the virtual tree is not necessarily binary. (2) Define a recursive structural decomposition of the tree ${{\mathcal T}}(X)$, with the property that certain blocks of this decomposition contain requests in non-overlapping time-intervals. (3) Describe a multi-finger strategy on ${{\mathcal T}}(X)$ for serving the requests, which induces a multi-finger strategy on $T$ with the required cost. (The strategy takes advantage of the decomposition in (2).)

We describe the steps more precisely, deferring some details to Appendix \[weakuniapp\].

##### The virtual tree. {#the-virtual-tree. .unnumbered}

Given a number $\ell$, $X \in [n]^m$, and a BST $T$ over $[n]$ with root $r$, the virtual tree ${{\mathcal T}}= {{\mathcal T}}{(\ell,T,X)}$ is a rooted tree with vertex-set $\{(i,x_{i}) \mid i\in[m]\}\cup\{(0,x_{0})\}$, where $x_0 = r$ is the root of $T$ and $(0,x_{0})$ is the root of ${{\mathcal T}}$. The *parent* of a non-root vertex $(i,x_{i})$ in ${{\mathcal T}}$ is $(j,x_{j})=\arg\min_{j \in [i-\ell,i)}\{d_{T}(x_{i},x_{j})\}$. In words, $(j,x_j)$ is the request at most $\ell$ steps before $(i,x_i)$, closest to $x_i$ (in $T$).

For each edge $e=((j,x_{j}),(i,x_{i}))$, we define the weight $w_{{{\mathcal T}}}(e)=d_{T}(x_{i},x_{j})+1$. For each subtree $H$ of ${{\mathcal T}}$, let $w_{{{\mathcal T}}}(H)$ be the total weight of its edges. Observe that $w_{{{\mathcal T}}}({{\mathcal T}})=\kmintree_{T}(X)$.

##### Structure and decomposition of the virtual tree. {#structure-and-decomposition-of-the-virtual-tree. .unnumbered}

We say that a vertex $(i,x_{i})$ is *before* (or *earlier than*) $(j,x_{j})$ if $i<j$, otherwise it is *after* (or *later than*). For every subtree $H$ of ${{\mathcal T}}$ we denote the earliest vertex in $H$ as ${\mathsf{start}}(H)$ and the latest vertex in $H$ as ${\mathsf{end}}(H)$. The *time-span* of $H$, denoted ${\mbox{\sf span}}(H)$, is $(t_{1},t_{2}]$ where $(t_{1},x_{t_{1}})={\mathsf{start}}(H)$ and $(t_{2},x_{t_{2}})={\mathsf{end}}(H)$, and $H$ is *active* at time $t$ if $t \in {\mbox{\sf span}}(H)$.

We describe a procedure to decompose ${{\mathcal T}}{(\ell,T,X)}$ into directed paths (for the purpose of analysis), defining the key notions of *$i$-body* and *$i$-core*. The procedure is called on a subtree $H$ of ${{\mathcal T}}$, and the top-level call is $\textsf{decompose}({{\mathcal T}},\ell)$.

------------------------------------------------------------------------

**procedure** $\textsf{decompose}(H,i)$:

1.  If $H$ has no edges, return.

2.  Let $C(H)$ be the path from ${\mathsf{start}}(H)$ to ${\mathsf{end}}(H)$.

3.  Call $C(H)$ an $i$-core of $H$, and call $H$ the $i$-body of $C(H)$.

4.  For each connected component $H'$ in $H\setminus C(H)$ invoke $\textsf{decompose}(H',i-1)$.

------------------------------------------------------------------------

Observe that ${{\mathcal T}}$ itself is an $\ell$-body. Each $i$-body $H$ consists of its $i$-core $C(H)$ and a set of $(i-1)$-bodies that are connected components in $H\setminus C(H)$. For each of those $(i-1)$-bodies $H'$, we say that $H$ is a *parent* of $H'$, defining a tree-structure over bodies. Observe that the number of ancestor bodies of an $i$-body (excluding itself) is $\ell-i$. We make a sequence of further structural observations about the virtual tree and its decomposition.

\[lem:struc\_decomp\]

(i) At every time $t$, there are at most $\ell$ active edges in ${{\mathcal T}}{(\ell,T,X)}$.

(ii) The $i$-cores of the decomposition, for $1\le i\le \ell$, partition the vertices of ${{\mathcal T}}$.

(iii) Let $H$ be an $i$-body. At any time during the time-span of $H$, among the $(i-1)$-bodies with parent $H$ at most $i-1$ are active.\[lem:i-1 active children\]

(iv) Let $H$ be an $i$-body. The $(i-1)$-bodies with parent $H$ can be partitioned into $(i-1)$ groups ${\cal H}_{1},\dots,{\cal H}_{i-1}$ such that, for $1\le j\le i-1$ and $H',H''\in{\cal H}_{j}$, the time-spans of $H'$ and $H''$ are disjoint.\[thm:separate group\]

##### The strategy for moving fingers. {#the-strategy-for-moving-fingers. .unnumbered}

For two vertices $(i,x_{i})$ and $(j,x_{j})$ in the virtual tree ${{\mathcal T}}= {{\mathcal T}}{(\ell,T,S)}$, *moving a finger* $f$ from $(i,x_{i})$ to $(j,x_{j})$ means the following: let $P=((i_{1},x_{i_{1}}),\dots,(i_{k},x_{i_{k}}))$ be the unique path from $(i,x_{i}) = (i_{1},x_{i_{1}})$ to $(j,x_{j})=(i_{\ell},x_{i_{\ell}})$ in ${{\mathcal T}}$. For $j=1,\dots,k-1$, we iteratively move a finger $f$ from $x_{i_{j}}$ to $x_{i_{j+1}}$ using $d_{T}(x_{i_{j}},x_{i_{j+1}})$ steps. Hence, the total number of steps is at most $w_{{{\mathcal T}}}(P)$. By *serving an access in an $i$-body $H$*, we mean that, for each $(j,x_{j})\in V(H)$, at time $j$ there is a finger move to $x_{j}$ in $T$. For each $i \le \ell$, let ${\mathsf{nf}}(i)$ be the number of fingers used for serving accesses in an $i$-body. We define ${\mathsf{nf}}(1)=1$ and ${\mathsf{nf}}(i)=1+(i-1)\cdot{\mathsf{nf}}(i-1)$, thus, by induction, ${\mathsf{nf}}(i)\le i!$ for all $i \leq \ell$.

We now describe the strategy for moving fingers. Let $F$ be a set of fingers where $|F|={\mathsf{nf}}(\ell)$. At the beginning all fingers are at $(0,x_0)$. (In the reference tree $T$, all fingers are initially at the root $x_0$.) For $1\le j\le m$, we call ${\mbox{\sf access}}({{\mathcal T}},F,(j,x_{j}))$, defined below for an $i$-body $H$, set of fingers $F$, and $u\in V(H)$.

------------------------------------------------------------------------

**procedure** $\textsf{access}(H,F,u)$: Let $C = C(H)$ be the $i$-core of $H$, with $C=\{u_{1},\dots,u_{k'}\}$, where $u_{k}$ is before $u_{k+1}$ for each $k$. For $1\le j\le i-1$, let ${\cal H}_{j}$ be the $j$-th group of the $(i-1)$-bodies with parent $H$ (${\cal H}_{j}$ defined in Lemma \[lem:struc\_decomp\](iv)). The $i$-bodies in ${\cal H}_{j}$ are ordered by their time-span. That is, suppose ${\cal H}_{j}=\{H'_{1},\dots,H'_{\ell'}\}$. For each $\ell$, if ${\mbox{\sf span}}(H'_{\ell})=(a_{1},a_{2}]$ and ${\mbox{\sf span}}(H'_{\ell+1})=(b_{1},b_{2}]$, then $a_{2}\le b_{1}$. Fingers in $F$ are divided into $i$ groups $F_{1},\dots,F_{i-1},\{f_{i}\}$, where $|F_{j}|={\mathsf{nf}}(i-1)$, for $j\le i-1$, and $f_{i}$ is a single finger.

1.  If $u\in C$, then move $f_{i}$ to $u$ from the predecessor node of $u$ in $C$. If $u={\mathsf{end}}(H)$, then move $F$ from ${\mathsf{end}}(H)$ to ${\mathsf{start}}(H)$.

2.  [Else let $u\in V(H')\setminus V(C)$ where $H'\in{\cal H}_{j}$. If $u = {\mathsf{start}}(H')$ and $H'$ is the first $(i-1)$-body in ${\cal H}_j$, move $F_j$ from ${\mathsf{start}}(H)$ to ${\mathsf{start}}(H')$. Perform ${\mbox{\sf access}}(H',F_{j},u)$. If $u={\mathsf{end}}(H')$ and if $H'$ is the last in ${\cal H}_{j}$ then move $F_{j}$ from ${\mathsf{start}}(H')$ to ${\mathsf{end}}(H)$. Otherwise, if $u={\mathsf{end}}(H')$ and there is a next $(i-1)$-body $H''$ in ${\cal H}_{j}$, then move $F_{j}$ from ${\mathsf{start}}(H')$ to ${\mathsf{start}}(H'')$.]{}

------------------------------------------------------------------------

In order to give the reader more intution, we give an alternative description. A $1$-body $H$ consists only of its $1$-core $C(H)$. We use one finger and move it through $C(H)$. For $i > 1$, an $i$-body $H$ decomposes in its $i$-core $C(H)$ and $i-1$ groups ${\cal H}_1$ to ${\cal H}_{i-1}$ of $(i-1)$-bodies. Initially, we have ${\mathsf{nf}}(i)$ fingers on ${\mathsf{start}}(H)$. We use one finger to move down the $i$-core. We use a group $F_j$ of ${\mathsf{nf}}(i-1)$ fingers for the $j$-group ${\cal H}_j$. Let $H_1$, …$H_p$ be the $(i-1)$-cores in ${\cal H}_j$. We first move $F_j$ to ${\mathsf{start}}(H_1)$. Then we use the strategy recusively to move $F_j$ through $H_1$. Once the group of fingers has reached ${\mathsf{end}}(H_1)$, we move them to ${\mathsf{start}}(H_2)$, and so on. Once the fingers have reached ${\mathsf{end}}(H_p)$, we move them back to ${\mathsf{start}}(H)$. We coordinate (this is not really necessary) the movement of the fingers by the order of the accesses in the access sequence $X$.

From the description of ${\mbox{\sf access}}$ it is clear that all accesses in ${{\mathcal T}}$ are served and that ${\mathsf{nf}}(\ell)$ fingers are sufficient. It remains to bound the total number of steps all fingers move. For an $i$-body $H$, let ${\mbox{\sf cost}}(H)$ be the total cost of calling ${\mbox{\sf access}}(H,F,u)$ for all $u\in H$. Let ${\cal H}$ denote the set of $(i-1)$-bodies with parent $H$. Let $C^{+}(H)$ denote the $i$-core $C(H)$ augmented with the edges connecting $C(H)$ to the $(i-1)$-bodies in ${\cal H}$. Then:

${\mbox{\sf cost}}(H)\le2\cdot{\mathsf{nf}}(i)\cdot w_{{{\mathcal T}}}(C^{+}(H))+\sum_{H'\in{\cal H}}{\mbox{\sf cost}}(H')$.\[thm:cost\_H\]

By induction, we obtain ${\mbox{\sf cost}}(H)\le2\cdot i!\cdot w_{{{\mathcal T}}}(H)$. (For $i=1$ we have $H = C(H)$.) Since ${\mathsf{nf}}(\ell)\le \ell!$, we have that ${\mbox{\sf F}}^{(\ell!)}_{T}(X)\le {\mbox{\sf F}}^{{\mathsf{nf}}(\ell)}_{T}(X) \leq {\mbox{\sf cost}}({{\mathcal T}})$. By the previous claim we have ${\mbox{\sf cost}}({{\mathcal T}})\le 2\cdot (\ell!)\cdot w_{{{\mathcal T}}}({{\mathcal T}})=2 \cdot (\ell!)\cdot\kmintree_{T}(X)$, concluding the proof.

##### Application 2. Decomposable sequences (Theorem \[thm:decomp\]). {#application-2.-decomposable-sequences-theoremthmdecomp. .unnumbered}

Let $\sigma = (\sigma(1),\ldots, \sigma(n))$ be a permutation. For $a,b: 1 \leq a< b \leq n$, we say that $[a,b]$ is a [*block*]{} of $\sigma$ if ${\left\{ \sigma(a),\ldots, \sigma(b) \right\}} = {\left\{ c,\ldots, d \right\}}$ for some integer $c,d \in [n]$. A [*block partition*]{} of $\sigma$ is a partition of $[n]$ into $k$ blocks $[a_i, b_i]$ such that $(\bigcup_i [a_i, b_i]) \cap {\ensuremath{\mathbb N}}= [n]$. For such a partition, for each $i=1,\ldots, k$, consider a permutation $\sigma_i\in S_{b_i -a_i+1}$ obtained as an order-isomorphic permutation when restricting $\sigma$ on $[a_i, b_i]$. For each $i$, let $q_i \in [a_i, b_i]$ be a representative element of $i$. The permutation $\tilde \sigma \in [k]^k$ that is order-isomorphic to ${\left\{ \sigma(q_1),\ldots, \sigma(q_k) \right\}}$ is called a [*skeleton*]{} of the block partition. We may view $\sigma$ as a [*deflation*]{} $\tilde \sigma[\sigma_1, \ldots, \sigma_k]$.

A permutation $\sigma$ is $d$-decomposable if $\sigma = (1)$, or $\sigma = \tilde \sigma[\sigma_1,\ldots, \sigma_{d'}]$ for some $d' \leq d$ and each permutation $\sigma_i$ is $d$-decomposable (we refer to [@FOCS15] for alternative definitions). Permutations that are $2$-decomposable are called *separable* [@separable], and this class includes preorder traversal sequences [@ST85] as a special case.

To show Theorem \[thm:decomp\], it is sufficient to define a reference tree $T$ and a one-finger strategy for serving a $d$-decomposable sequence $X$ in $T$ with cost $O(\log{d}) \cdot |X|$. (Appendix \[app:decomp\].)

Combined with the Iacono-Langerman result [@LI16] that Greedy BST has the lazy finger property, we conclude that the cost of Greedy on any $d$-decomposable sequence $X$ is at most $O(\log d)\cdot |X|$. The result is tight and strengthens our earlier bound [@FOCS15] of $|X| \cdot 2^{O(d^{2})}$.

##### Application 3. Generalized monotone sequences. {#application-3.-generalized-monotone-sequences. .unnumbered}

A sequence $X \in [n]^m$ is *$k$-monotone*, if it can be partitioned into $k$ subsequences (not necessarily contiguous), all increasing or all decreasing. This property has been studied in the context of adaptive sorting, and special-purpose structures have been designed to exploit the $k$-monotonicity of input sequences (see e.g. [@Moffat; @Levcopoulos]). Our results show that BSTs can also adapt to such structure.

Let $X$ be a $k$-monotone sequence. Then ${\mbox{\sf F}}^k(X)=O(k) \cdot |X|$.

It follows that ${\mbox{\sf OPT}}(X) \leq O(k \log {k}) \cdot |X|$ for $k$-monotone sequences.[^11] The simulation is straightforward. Let $\{X_1, \dots, X_k\}$ be a partitioning of $X$ into increasing sequences (such a partition can be found online). Let $T$ be an arbitrary static BST over $[n]$. Consider $k$ fingers $f_{1},\dots,f_{k}$, initially all on $1$. For accessing $x_j \in X_i$, move finger $f_i$ to $x_j$. Observe that over the entire sequence $X$, each finger does only an in-order traversal of $T$, taking $O(n)$ steps. Thus, ${\mbox{\sf F}}^k_{T}(X)=O(nk)$. A lower bound of $\Omega(n \log{k})$ follows from enumerative results: for sufficiently large $n$, the number of $k$-monotone permutations $X \in [n]^n$ is at least $k^{\Omega(n)}$ (implied by e.g. [@regev1981]). Therefore, by a standard information-theoretic argument (see e.g. [@Blum Thm. 4.1]), there exists a $k$-monotone permutation $X \in [n]^n$ with ${\mbox{\sf OPT}}(X) = \Omega(n \log k)$.

##### Further results. {#sec5 .unnumbered}

\[sec:separation\]

We state our hierarchy result (Theorem \[thm:hierarchyx\]), also implying a weak separation between $k$-finger bounds and “monotone” bounds.

\[thm:hierarchy\] For all $k$ and infinitely many $n$, there is a $k$-monotone sequence $S_k$ of length $n$, such that:

-   $F^{k-1}(S_k) = \Omega(\frac{n}{k} \log (n/k))$

-   $F^{k}(S_k) = O(n)$ (independent of $k$).

In addition, we show a separation between the $k$-finger property and the working set property, showing that for all $k$ and infinitely many $n$, there are sequences $S$ and $S'$ of length $n$, such that ${\mbox{\sf WS}}(S) = o({\mbox{\sf F}}^{k}(S))$, and ${\mbox{\sf F}}^{k}(S') = o({\mbox{\sf WS}}(S))$. (Appendix \[sec:WS-LF\].)

#### Acknowledgements {#acknowledgements .unnumbered}

Parinya Chalermsook is supported by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 759557) and by Academy of Finland Research Fellows, under grant No. 310415. László Kozma is supperted through ERC consolidator grant No. 617951. Thatchaphol Saranurak is supported by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 715672, and by the Swedish Research Council (Reg. No. 2015-04659).

We thank Nikhil Bansal and Greg Koumoutsos for insightful discussions.

Offline BST simulation {#sec:simulation lazy fingers}
======================

BST simulation of a deque {#deque_proof}
-------------------------

\[prop:DequeBST\]The minimum and maximum element from a BST-based deque can be deleted in $O(1)$ amortized operations.

The simulation is inspired by the well-known simulation of a queue by two stacks with constant amortized time per operation ([@Mehlhorn-Sanders:Toolbox Exercise 3.19]). We split the deque at some position (determined by history) and put the two parts into structures that allow us to access the first and the last element of the deque. It is obvious how to simulate the deque operations as long as the sequences are non-empty. When one of the sequences becomes empty, we split the other sequence at the middle and continue with the two parts. A simple potential function argument shows that the amortized cost of all deque operations is constant. Let $\ell_1$ and $\ell_2$ be the length of the two sequences, and define the potential $\Phi = |\ell_1 - \ell_2|$. As long as neither of the two sequences are empty, for every insert and delete operation both the cost and the change in potential are $O(1)$. If one sequence becomes empty, we split the remaining sequence into two equal parts. The decrease in potential is equal to the length of the sequence before the splitting (the potential is zero after the split). The cost of splitting is thus covered by the decrease of potential.

The simulation by a BST is easy. We realize both sequences by chains attached to the root. The right chain contains the elements in the second stack with the top element as the right child of the root, the next to top element as the left child of the top element, and so on.

Extended hand {#appa2}
-------------

To describe the simulation precisely, we borrow terminology from [@CombineBST; @persistent_tries]. Let $T$ be a BST with a set $F$ of $k$ fingers $f_{1},\dots,f_{k}$. For convenience we assume the root of $T$ to be one of the fingers. Let $S(T,F)$ be the Steiner tree with terminals $F$. A *knuckle* is a connected component of $T$ after removing $S(T,F)$, i.e. a hanging subtree of $T$. Let $P(T,F)$ be the union of fingers and the degree-3 nodes in $S(T,F)$. We call $P(T,F)$ the set of *pseudofingers*. A *tendon* $\tau_{x,y}$ is the path connecting two pseudofingers $x,y\in P(T,F)$ (excluding $x$ and $y$) such that there is no other $z\in P(T,F)$ inside. We assume that $x$ is an ancestor of $y$.

The next terms are new. For each tendon $\tau_{x,y}$, there are two *half tendons,* $\tau_{x,y}^{<},\tau_{x,y}^{>}$ containing all elements in $\tau_{x,y}$ which are less than $y$ and greater than $y$ respectively. Let $H(T,F)=\{\tau_{x,y}^{<},\tau_{x,y}^{>}\mid\tau_{x,y}$ is a tendon$\}$ be the set of all half tendons.

For each $\tau\in H(T,F)$, we can treat $\tau$ as an interval $[\min(\tau),\max(\tau)]$ where $\min(\tau),\max(\tau)$ are the minimum and maximum elements in $\tau$ respectively. For each $f\in P(T,F)$, we can treat $f$ as an trivial interval $[f,f]$.

Let $E(T,F)=P(T,F)\cup H(T,F)$ be the set of intervals defined by all pseudofingers $P(T,F)$ and half tendons $H(T,F)$. We call $E(T,F)$ an *extended hand*[^12]. Note that when we treat $P(T,F)\cup H(T,F)$ as a set of elements, such a set is exactly $S(T,F)$. So $E(T,F)$ can be viewed as a partition of $S(T,F)$ into pseudofingers and half-tendons. Figure \[ExtendedHand\] illustrates these definitions.

![\[ExtendedHand\] The pseudofingers are $b$, $d$, and $h$. The half-tendons $\tau_{h,b}^<$ and $\tau_{h,b}^>$ are $a$ and $g,f$. The intervals in $E(T,F)$ are $[a,a]$, $[b,b]$, $[c,c]$, $[d,d]$, $[f,g]$, and $[h,h]$. ](SimBST.pdf){width="30.00000%"}

We first state two facts about the extended hand.

\[lem:hand size\]Given any $T$ and $F$ where $|F|=k$, there are $O(k)$ intervals in $E(T,F)$.

Note that $|P(T,F)|\le2k$ because there are $k$ fingers and there can be at most $k$ nodes with degree 3 in $S(T,F)$. Consider the graph where pseudofingers are nodes and tendons are edges. That graph is a tree. So $|H(T,F)|=O(k)$ as well.

\[lem:hand ordered\]Given any $T$ and $F$, all the intervals in $E(T,F)$ are disjoint.

Suppose that there are two intervals $\tau,x\in E(T,F)$ that intersect each other. One of them, say $\tau$, must be a half tendon. Because the intervals of pseudofingers are of length zero and they are distinct, they cannot intersect. We write $\tau=\{t_{1},\dots,t_{k}\}$ where $t_{1}<\dots<t_{k}$. Assume w.l.o.g. that $t_{i}$ is an ancestor of $t_{i+1}$ for all $i<k$, and so $t_{k}$ is an ancestor of a pseudofingers $f$ where $t_{k}<f$.

Suppose that $x$ is a pseudofinger and $t_{j}<x<t_{j+1}$ for some $j$. Since $t_{j}$ is the first left ancestor of $t_{j+1}$, $x$ cannot be an ancestor of $t_{j+1}$ in $T$. So $x$ is in the left subtree of $t_{j+1}$. But then $t_{j+1}$ is a common ancestor of two pseudofingers $x$ and $f$, and $t_{j+1}$ must be a pseudofinger which is a contradiction.

Suppose next that $x=\{x_{1},\dots,x_{\ell}\}$ is a half tendon where $x_{1}<\dots<x_{\ell}$. We claim that either $[x_{1},x_{\ell}]\subset[t_{j},t_{j+1}]$ for some $j$ or $[t_{1},t_{k}]\subset[x_{j'},x_{j'+1}]$ for some $j'$. Suppose not. Then there exist two indices $j$ and $j'$ where $t_{j}<x_{j'}<t_{j+1}<x_{j'+1}$. Again, $x_{j'}$ cannot be an ancestor of $t_{j+1}$ in $T$, so $x_{j'}$ is in the left subtree of $t_{j+1}$. We know either $x_{j'}$ is the first left ancestor of $x_{j'+1}$ or $x_{j'+1}$ is the first right ancestor of $x_{j'}$. If $x_{j'}$ is an ancestor of $x_{j'+1}$, then $x_{j'+1}<t_{j+1}$ which is a contradiction. If $x_{j'+1}$ is the first right ancestor of $x_{j'}$, then $t_{j+1}$ is not the first right ancestor of $x_{j'}$ and hence $x_{j'+1}<t_{j+1}$ which is a contradiction again. Now suppose w.l.o.g. $[x_{1},x_{\ell}]\subset[t_{j},t_{j+1}]$. Then there must be another pseudofinger $f'$ in the left subtree of $t_{j+1}$, hence $\tau$ cannot be a half tendon, which is a contradiction.

The structure of the simulating BST {#appa3}
-----------------------------------

In this section, we describe the structure of the BST $T'$ that we maintain given a $k$-finger BST $T$ and the set of fingers $F$.

For each half tendon $\tau\in H(T,F)$, let $T'_{\tau}$ be the tree with $\min(\tau)$ as a root which has $\max(\tau)$ as a right child. $\max(\tau)$’s left child is a subtree containing the remaining elements $\tau\setminus\{\min(\tau),\max(\tau)\}$. We implement a *BST simulation of a deque* on this subtree as defined in Appendix \[deque\_proof\]. By Lemma \[lem:hand ordered\], intervals in $E(T,F)$ are disjoint and hence they are totally ordered. Since $E(T,F)$ is an ordered set, we can define $T'_{E_{0}}$ to be a balanced BST such that its elements correspond to elements in $E(T,F)$. Let $T'_{E}$ be the BST obtained from $T'_{E_{0}}$ by replacing each node $a$ in $T'_{E_{0}}$ that corresponds to a half tendon $\tau\in H(T,F)$ by $T'_{\tau}$. That is, suppose that the parent, left child, and right child are $a_{{up}},a_{l}$ and $a_{r}$ respectively. Then the parent in $T'_{E}$ of the root of $T'_{\tau}$ which is $\min(\tau)$ is $a_{up}$. The left child in $T'_{E}$ of $\min(\tau)$ is $a_{l}$ and the right child in $T'_{E}$ of $\max(\tau)$ is $a_{r}$.

The BST $T'$ has $T'_{E}$ as its top part and each knuckle of $T$ hangs from $T'_{E}$ in a determined way.

\[lem:depth pseudofinger\]Each element corresponding to pseudofinger $f\in P(T,F)$ has depth $O(\log k)$ in $T'_{E}$, and hence in $T'$.

By Lemma \[lem:hand size\], $|E(T,F)|=O(k)$. So the depth of $T'_{E_{0}}$ is $O(\log k)$. For each node $a$ corresponding to a pseudofinger $f\in P(T,F)$, observe that the depth of $a$ in $T'_{E}$ is at most twice the depth of $a$ in $T'_{E_{0}}$ by the construction of $T'_{E}$.

The cost for simulating the $k$-finger BST {#appa4}
------------------------------------------

We finally prove the claim on the cost of our BST simulation, which immediately implies Theorem \[thm: LF simulation\]. That is, we prove that whenever one of the fingers in a $k$-finger BST $T$ moves to its neighbor or rotates, we can update the maintained BST $T'$ to have the structure as described in the last section with cost $O(\log k)$.

We state two observations which follow from the structure of our maintained BST $T'$ described in \[appa3\]. The first observation follows immediately from Lemma \[prop:DequeBST\].

\[lem:update tendon\]For any half tendon $\tau\in H(T,F)$, we can insert or delete the minimum or maximum element in $T'_{\tau}$ with cost $O(1)$ amortized.

Next, it is convenient to define a set $A$, called *active set*, as a set of pseudofingers, the roots of knuckles whose parents are pseudofingers, and the minimum or maximum of half tendons.

\[lemma:change exended hand\]When a finger $f$ in a $k$-finger BST $T$ moves to its neighbor or rotates with its parent, the extended hand $E(T,F)=P(T,F)\cup H(T,F)$ is changed as follows.

1.  There are at most $O(1)$ half tendons $\tau\in H(T,F)$ whose elements are changed. Moreover, for each changed half tendon $\tau$, either the minimum or maximum is inserted or deleted. The inserted or deleted element $a$ was or will be in the active set $A$.

2.  There are at most $O(1)$ elements added or removed from $P(T,F)$. Moreover, the added or removed elements were or will be in the active set $A$.

\[lem:active set\]Let $a\in A$ be an element in the active set. We can move $a$ to the root with cost $O(\log k)$ amortized. Symmetrically, the cost for updating the root $r$ to become some element in the active set is $O(\log k)$ amortized.

There are two cases. If $a$ is a pseudofinger or a root of a knuckle whose parent is pseudofinger, we know that the depth of $a$ was $O(\log k)$ by Lemma \[lem:depth pseudofinger\]. So we can move $a$ to root with cost $O(\log k)$. Next, if $a$ is the minimum or maximum of a half tendon $\tau$, we know that the depth of the root of the subtree $T'_{\tau}$ is $O(\log k)$. Moreover, by Lemma \[lem:update tendon\], we can delete $a$ from $T'_{\tau}$ (make $a$ a parent of $T'_{\tau}$) with cost $O(1)$ amortized. Then we move $a$ to root with cost $O(\log k)$ worst-case. The total cost is then $O(\log k)$ amortized. The proof for the second statement is symmetric.

\[lem:update cost\]When a finger $f$ in a $k$-finger BST $T$ moves to its neighbor or rotates with its parent, the BST $T'$ can be updated accordingly with cost $O(\log k)$ amortized.

According to Lemma \[lemma:change exended hand\], we separate our cost analysis into two parts.

For the fist part, let $a\in A$ be the element to be inserted into a half tendon $\tau$. By Lemma \[lem:active set\], we move $a$ to root with cost $O(\log k)$ and then insert $a$ as a minimum or maximum element in $T'_{\tau}$ with cost $O(\log k)$. Deleting $a$ from some half tendon with cost $O(\log k)$ is symmetric.

For the second part, let $a\in A$ be the element to be inserted into a half tendon $\tau$. By Lemma \[lem:active set\] again, we move $a$ to root and move back to the appropriate position in $T'_{E_{0}}$ with cost $O(\log k)$. We also need rebalance $T'_{E_{0}}$ but this also takes cost $O(\log k)$.

Finally, we describe the BST simulation of a $k$-finger execution with overhead $O(\log k)$. Let $A$ be an arbitrary $k$-finger execution in BST $T$. Whenever there is an update in $T$ (i.e. a finger moves to its neighbor or rotates), we update the BST $T'$ according to Lemma \[lem:update cost\] with cost $O(\log k)$ amortized. The BST $T'$ is maintained so that its structure is as described in Appendix \[appa3\]. By Lemma \[lem:depth pseudofinger\], we can access any finger $f$ of $T$ from the root of $T'$ with cost $O(\log k)$. Therefore, the cost of the BST execution is at most $O(\log k)$ times the cost of $A$. This concludes the proof.

Missing proofs for Application 1 {#weakuniapp}
================================

Proof of Lemma \[lem:struc\_decomp\] {#app:struc_decomp}
------------------------------------

##### Part (i) {#part-i .unnumbered}

 \
Suppose that there is some time $t$ when there are $\ell'>\ell$ edges $\{(j_{k},x_{j_{k}}),(i_{k},s_{i_{k}})\}_{k=1}^{\ell'}$ such that $j_{k}<t\le i_{k}$ for all $k\le \ell'$. Since each node has a unique parent, $i_{1},\dots,i_{\ell'-1}, i_{\ell'}$ must be distinct and hence $\max_{1 \le k \le \ell'} i_{k} \ge t + \ell' - 1 \ge t+\ell$. Thus $\max_{1 \le k \le \ell'} j_{k} \ge t$, a contradiction.

##### Part (ii) {#part-ii .unnumbered}

 \
By construction, the cores are edge-disjoint, and every vertex belongs to some core (the recurrence ends on singleton vertices only). It remains to show that when $\textsf{decompose}(H,0)$ is called during the execution of $\textsf{decompose}({{\mathcal T}},\ell)$, $H$ has no edges, i.e. there is no $i$-core or $i$-body with $i \leq 0$.

To see this, define the sequence of graphs $H_{0},\dots,H_{\ell}$ where $H_{\ell}={{\mathcal T}}{(\ell,T,X)}$, $H_{i-1}$ is a connected component of $H_{i}\setminus C(H_{i})$, and $H_{0}=H$. Recall that ${\mbox{\sf span}}(K)$ denotes the time-span of $K$. By definition of $C(H_{i})$, we have ${\mbox{\sf span}}(H_{i-1}) \subseteq {\mbox{\sf span}}(H_{i})$.

Suppose for contradiction that $H_{0}$ has an edge. Denote ${\mbox{\sf span}}(H_0) = (t_{1},t_{2}]$, where $t_{1}<t_{2}$. For all $0\le i\le \ell$, it holds that ${\mbox{\sf span}}(H_{i}) \supseteq (t_{1},t_{2}]$. Let $t\in(t_{1},t_{2}]$. We have that $C(H_{i})$ contains an edge $((a_{i},x_{a_{i}}),(b_{i},x_{b_{i}}))$ where $a_{i}<t\le b_{i}$ for all $0\le i\le \ell$. Since $C(H_{i})$ are edge-disjoint, this contradicts part (i).

##### Part (iii) {#part-iii .unnumbered}

 \
Suppose there are $i$ active $(i-1)$-bodies $H'_{1},\dots,H'_{i}$ of $H$ at time $t$. Since $H$ is an $i$-body, there are $\ell-i$ ancestors $A_{1},\dots,A_{\ell-i}$ of $H$. For each of the cores $C\in\{C(H'_{1}),\dots,C(H'_{i}),C(H),C(A_{1}),\dots,C(A_{\ell-i}$)} which is a set of size $\ell+1$, there is an edge $(a,s_{a}),(b,s_{b})$ where $a<t\le b$. This contradicts part (i).

##### Part (iv) {#part-iv .unnumbered}

 \
We construct the decomposition greedily. Consider the $(i-1)$ bodies $H'$ ordered by ${\mathsf{start}}(H')$ and put $H'$ into the group ${\cal H}_j$ for the smallest index $j$ such that the time-span of $H'$ is disjoint from the time-spans of all members of the group. Assume that this process opens up $i' > i-1$ groups. Then there are $(i-1)$-bodies $H'_1$ to $H'_{i'}$ (one per group) such that the time-span of the $i$-body $H$ intersects the time-spans of $H'_1$ to $H'_{i'}$, contradicting part (iii).

Proof of Lemma \[thm:cost\_H\] {#app:finger}
------------------------------

We analyze the total cost of calling ${\mbox{\sf access}}(H,F,u)$ for all $u\in V(H)$. The total cost due to recursive calls in Step 2 is accounted by the term $\sum_{H'\in {\cal H}}{\mbox{\sf cost}}({H'})$. The remaining operations amount to moving ${\mathsf{nf}}(i)$ fingers from ${\mathsf{start}}(H)$ to ${\mathsf{end}}(H)$ and back, along the $i$-core $C(H)$. The cost of this is exactly $2 \cdot {\mathsf{nf}}(i)\cdot w_{{{\mathcal T}}}(C(H))$. In addition we need to traverse, using ${\mathsf{nf}}(i-1)$ fingers, the edges connecting $C(H)$ to ${\mathsf{start}}(H')$, twice for all $H'\in {\cal H}$. The total cost thus becomes at most $2 \cdot {\mathsf{nf}}(i)\cdot w_{{{\mathcal T}}}(C^{+}(H)) + \sum_{H'\in {\cal H}}{\mbox{\sf cost}}({H'}) $.

We argue now by induction that for an $i$-body $H$, we have ${\mbox{\sf cost}}(H)\le2\cdot i!\cdot w_{{{\mathcal T}}}(H)$. For $i=1$, $H=C(H)=C^{+}(H)$. Thus, by the inductive step: $${\mbox{\sf cost}}(H) \le 2 \cdot {\mathsf{nf}}(1)\cdot w_{{{\mathcal T}}}(C^{+}(H))
 \le 2 \cdot w_{{{\mathcal T}}}(H).$$ For the general inductive step: $$\begin{aligned}
{\mbox{\sf cost}}(H) & \le 2 \cdot {\mathsf{nf}}(i)\cdot w_{{{\mathcal T}}}(C^{+}(H))+\sum_{H'\in{\cal H}} {\mbox{\sf cost}}({H'}) \\
& \le 2\cdot i!\cdot w_{{{\mathcal T}}}(C^{+}(H))+\sum_{H' \in {\cal H}}2\cdot(i-1)!\cdot w_{{{\mathcal T}}}(H')\\
 & \le 2\cdot i!\cdot \Bigl(w_{{{\mathcal T}}}(C^{+}(H))+\sum_{H' \in {\cal H}} w_{{{\mathcal T}}}(H') \Bigr)\\
 & = 2\cdot i!\cdot w_{{{\mathcal T}}}(H). \end{aligned}$$

Decomposable Sequences {#app:decomp}
======================

Let $X = (x_1,\ldots, x_n)$ be a $k$-decomposable permutation of length $n$. Then ${\mbox{\sf F}}^1(X) \le 4({\lvert X\rvert} - 1) {\ensuremath{\left\lceil\log k\right\rceil}}$.

It is sufficient to define a reference tree $T$ for which ${\mbox{\sf F}}^1_T(X)$ achieves such bound. We remark that the tree will have auxiliary elements. We construct $T$ recursively. If $X$ has length one, then $T$ has a single node and this node is labeled by the key in $X$. Clearly, ${\mbox{\sf F}}^1_T(X) = 0$. Otherwise, let $X = \tilde X[X_1,\ldots,X_j]$ with $j \in [k]$ be the outermost partition of $X$. Denote by $T_i$ the tree for $X_i$ that has been inductively constructed. Let $T_0$ be a BST of depth at most ${\ensuremath{\left\lceil\log j\right\rceil}}$ and with $j$ leaves. Identify the $i$-th leaf with the root of $T_i$ and assign keys to the internal nodes of $T_0$ such that the resulting tree is a valid BST. Let $r_i$ be the root of $T_i$, $0 \le i \le j$ and let $r = r_0$ be the root of $T$. Then

$$\begin{aligned}
d_T(r,x_1) & \le {\ensuremath{\left\lceil\log k\right\rceil}} + d_{T_1}(r_1,x_1) \\
d_T(r,x_n) & \le  {\ensuremath{\left\lceil\log k\right\rceil}} + d_{T_j}(r_j,x_n) \\
d_T(x_{t-1},x_t) & \le  \begin{cases} d_{T_\ell}(x_{t-1},x_t)    & \text{if $x_{t-1},x_t \in X_\ell$}\\
                    2{\ensuremath{\left\lceil\log k\right\rceil}} + d_{T_\ell}(r_\ell,x_{t-1}) + d_{T_{\ell + 1}}(r_{\ell+1},x_t)  &\text{if $x_{t-1} \in X_\ell$ and $x_t \in X_{\ell + 1}$,}\end{cases}\end{aligned}$$ and hence $$\begin{aligned}
{\mbox{\sf F}}^1_T(X) & = d_T(r,x_0) + \sum_{t \ge 2} d_T(x_{t-1},x_t) + d_T(x_n,r) \\
    &\le 2j {\ensuremath{\left\lceil\log k\right\rceil}}+ \sum_{1 \le \ell \le j} {\mbox{\sf F}}^1_{T_{\ell}}(X_{\ell}) \quad
\le \quad 2j  {\ensuremath{\left\lceil\log k\right\rceil}} + \sum_{1 \le \ell \le j} 4({\lvert X_\ell\rvert} - 1) {\ensuremath{\left\lceil\log k\right\rceil}}\\
    &\le (2j - 4j + 4\sum_{1 \le \ell \le j} {\lvert X_\ell\rvert}) {\ensuremath{\left\lceil\log k\right\rceil}}\ \  \le \ \ 4({\lvert X\rvert} - 1){\ensuremath{\left\lceil\log k\right\rceil}},\end{aligned}$$ where the last inequality uses $j \ge 2$.

Finger bounds with auxiliary elements 
======================================

Recall that ${\mbox{\sf F}}(X)$ is defined as the minimum over all BSTs $T$ on $[n]$ of ${\mbox{\sf F}}_T(X)$. It is convenient to define a slightly stronger finger bound that also allows [*auxiliary elements*]{}. Define $\widehat{{\mbox{\sf F}}}(X)$ as the minimum over all BSTs $T$ that contain the keys $[n]$ (but the size of $T$ can be much larger than $n$). We define $\widehat{{\mbox{\sf F}}}^k(X)$ as the $k$-finger bound when the tree is allowed to have auxiliary elements. We argue that the two definitions are equivalent.

For any integer $k$, ${\mbox{\sf F}}^k(X)=\Theta(\widehat{{\mbox{\sf F}}}^k(X))$ for all $X$.

It is clear that $\widehat{{\mbox{\sf F}}}^k(X)\le {\mbox{\sf F}}^k(X)$. We only need to show the converse.

Let $T$ be a BST (with auxiliary elements) such that ${\mbox{\sf F}}^k_{T}(X)=\widehat{{\mbox{\sf F}}}^k(X)$. Denote by $\vec{f}$ the optimal finger strategy on $T$. Let $[n]\cup Q$ be the elements of $T$ where $Q$ is the set of auxiliary elements in $T$. For each $a\in[n]\cup Q$, let $d_{T}(a)$ be the depth of key $a$ in $T$, and let $w(i)=4^{-d_T(i)}$. For any two elements $i$ and $j$ and set $Y \subseteq [n] \cup Q$, let $w_{Y}[i:j]$ be the [sum $\sum_{k \in Y\cap [i,j]} w(k)$ of the weights of the elements in $Y$ between $i$ and $j$ (inclusive).]{} For any $i,j\in[n]\cup Q$ such that $i\leq j$, we have $$\log\frac{w_{[n]\cup Q}[i:j]}{\min(w(i),w(j))}=O(d_{T}(i,j)),$$ where $d_{T}(i,j)$ is the distance from $i$ to $j$ in $T$. So, this same bound also holds when considering only keys in $[n]$. That is, for $i,j \in [n]$, we have $$\log\frac{w_{[n]}[i:j]}{\min(w(i),w(j))}=O(d_{T}(i,j)).$$

Given the weight of $\{w(a)\}_{a\in[n]}$, the BST $T'$ (without auxiliary elements) is constructed by invoking Lemma \[thm:tree-from-weight\]. We bound the term ${\mbox{\sf F}}^k_{T'}(X)$ (using strategy $\vec{f}$) by $$O( \sum_{t} d_{T'}(x_{\sigma(f_t,t)}, x_t)) = O(\sum_{t=1}^{m-1}\lg\frac{w_{[n]}[x_{t}:x_{\sigma(f_t,t)}]}{\min(w(x_{i}),w(x_{\sigma(f_t,t)}))})=O(\sum_{t=1}^{m-1}d_{T}(x_{\sigma(f_t,t)},x_{t}))=O({\mbox{\sf F}}^k_{T}(X))$$ where $X=(x_{1},\dots,x_{m})$. Therefore, ${\mbox{\sf F}}^k(X)\le {\mbox{\sf F}}^k_{T'}(X)=O({\mbox{\sf F}}^k_{T}(X))=O(\widehat{{\mbox{\sf F}}}^k(X))$.

Given a weight function $w(\cdot)$, and $W = \sum_{i\in[n]}{w(i)}$, there is a deterministic construction of a BST $T_w$ such that the depth of every key $i \in [n]$ is $d_{T_w}(i) = O(\log \frac{W}{w(i)})$. \[thm:tree-from-weight\]

Let $w_1$, …$w_n$ be a sequence of weights. We show how to construct a tree in which the depth of element $\ell$ is $O(\log w[1:\ell]/\min(w_1,w_\ell))$.

For $i \ge 1$, let $j_i$ be minimal such that $w[1:j_i] \ge 2^i w_1$. Then $w[1:j_i - 1] < 2^i w_1$ and $w[j_{i-1} + 1 : j_i] \le 2^{i-1} w_1 + w_{j_i}$.

Let $T_i$ be the following tree. The right child of the root is the element $j_i$. The left subtree is a tree in which element $\ell$ has depth $O(\log 2^{i-1} w_1/w_\ell)$.

The entire tree has $w_1$ in the root and then a long right spine. The trees $T_i$ hang off the spine to the left. In this way the depth of the root of $T_i$ is $O(i)$.

Consider now an element $\ell$ in $T_i$. Assume first that $\ell \not= j_i$. The depth is $$O\left(i + \log \frac{2^{i-1} w_1}{w_\ell}\right) = O\left(i + \log \frac{2^{i-1} w_1}{\min(w_1,w_\ell)}\right)= 
O\left(\log \frac{2^{i-1} w_1}{\min(w_1,w_\ell)}\right)= O\left(\frac{w[1:\ell]}{\min(w_1,w_\ell)}\right).$$

For $\ell = j_i$, the depth is $$O\left(i\right) = O\left( \log \frac{2^i w_1}{w_1} \right) = O\left(\log \frac{w[1:j_i]}{\min(w_1,w_{j_i})}\right) .$$

All bounds are derived via information-theoretic arguments. To avoid the need to do probabilistic analysis, we use instead the language of Kolmogorov complexity, which is applicable to a specific input, rather than a distribution on inputs. First, we state the following proposition.

\[prop:K less than OPT\] For any sequence $S$, let $K(S)$ denote Kolmogorov complexity of $S$. We have $K(S) = O({\mbox{\sf OPT}}(S)) $.

We also use the following standard fact in the theory of Kolmogorov complexity.

Let ${{\mathcal{S}}}$ be a subset of sequences in $[n]^m$. There exists a sequence $S \in {{\mathcal{S}}}$ with $K(S) = \Omega(\log |{{\mathcal{S}}}|)$.

We are now ready to derive all bounds.

\[$k$-lazy fingers\] For each $k$ (possibly a function that depends on $n$), there are infinitely many sequences $X$, for which ${\mbox{\sf LF}}{k}(S) \cdot \log k\le {\mbox{\sf OPT}}(S)$.

Let $J \subseteq [n]: |J| = k$. We choose a sequence $S\in J^m$ that has Kolmogorov complexity at least $K(S) = \Omega(m \log k)$, so we have ${\mbox{\sf OPT}}(S) = \Omega(m \log k)$. Now we argue that the lazy finger cost is low. Choose the reference tree as an arbitrary balanced tree $T$. Notice that the lazy finger bound is ${\mbox{\sf LF}}{k}_T(S) =O(m)$: Initial fingers can be chosen to be the location of keys in $J$. Afterwards, each key in $J$ is served by its private finger.

For each $k$, there are infinitely many sequences $S$ for which $m(S) = k$, and $K(S) \geq |S| \cdot \log k$.

This follows from the result of Regev [@regev1981] (who proved much more general results) which implies that for sufficiently large $n$, the number of permutations $S \in [n]^n$ that avoid $(1,\ldots, k)$ is at least $k^{\Omega(n)}$. Therefore, there exists a permutation $S$ with $K(S) = \Omega(n \log k)$.

Proof of Theorem \[thm:hierarchyx\] {#sec:proof-hierarchy}
===================================

Let $n$ be an integer multiple of $k$ and $\ell = n/k$. Consider the tilted $k$-by-$\ell$ grid $S_k$. More precisely, the access sequence is defined as: $1$, $\ell + 1$, …, $\ell \cdot(k-1) + 1$, $2$, $\ell+2$, …, $(k-1)\ell +2$,…, $(k-1)\ell +\ell$. We denote the elements of $S_k$ as $s_i$, for $i=1,\dots,n$. To see the geometry of this sequence, one may view it as a partitioning of the keys $[n]$ into “blocks” ${{\mathcal{B}}}_i: i =1,\ldots, k$ where ${{\mathcal{B}}}_i$ contains the keys in $\{\ell (i-1) +1, \ell (i-1) +2, \ldots, \ell i\}$, so we have $|{{\mathcal{B}}}_i | = \ell$ and $\bigcup_{i=1}^k {{\mathcal{B}}}_i = [n]$. The sequence $S_k$ consists of an interleaving of an increasing traversal of each block.

${\mbox{\sf F}}^k(S_k) = O(n)$.

The main idea is to use each finger to serve only the keys inside blocks and to use a separate finger for each block. (recall that there are $k$ blocks and $k$ fingers.) We create a reference tree $T$ and argue that ${\mbox{\sf F}}^k_T(S_k) = O(n)$. Let $T_0$ be a BST of height $O(\log k)$ and with $k$ leaves. Each leaf of $T_0$ corresponds to the keys ${\left\{ \ell \cdot (i-1) +\frac 1 2 \right\}}_{i=1}^k$. The non-leafs of $T_0$ are assigned arbitrary fractional keys that are consistent with the BST properties. For each $i \in [k]$, path $P_i$ is defined as a BST with key $\ell \cdot (i-1) +1$ (i.e. the smallest key in block ${{\mathcal{B}}}_i$) at the root, where for each $j = 0, \ldots, (\ell-1)$, the key $\ell (i-1)+j$ has $\ell (i-1)+ (j+1)$ as its only (right) child. The final tree $T$ is obtained by hanging each path $P_i$ as a left subtree of a leaf $\ell \cdot (i-1) +\frac 1 2$. The $k$-finger strategy is simple: The $i$-th finger only takes care of the elements in block ${{\mathcal{B}}}_i$. The cost for the first access in block ${{\mathcal{B}}}_i$ is $O(\log k)$, and afterwards, the cost is only $O(1)$ per access. So the total access cost is $O(\frac{n}{k} \log k + n) = O(n)$.

${\mbox{\sf OPT}}(S_k) = O(n)$

Let $S_k^{(i)}$ be obtained from $S_k$ by restriction to ${{\mathcal{B}}}_i$ for each $i=1,\dots,k$. Let $\tilde{S}_k=(\tilde{s}_1,\dots,\tilde{s}_n ) \in [k]^n$ where $\tilde{s}_j = i$ iff $s_j \in {{\mathcal{B}}}_i$. By \[thm:interleaving\], ${\mbox{\sf OPT}}(S_k) \le \sum_{i=1}^k {\mbox{\sf OPT}}(S_k^{(i)}) + O({\mbox{\sf OPT}}(\tilde{S}_k))$. But, for each $i$, ${\mbox{\sf OPT}}(S_k^{(i)}) = O(\ell)$ because $S_k^{(i)}$ is just a sequential access of size $\ell$. ${\mbox{\sf OPT}}(\tilde{S}_k) = O(k\cdot \ell) = O(n)$ because $\tilde{S}_k$ a sequential access of size $k$ repeated $\ell$ times. Therefore, ${\mbox{\sf OPT}}(S_k) = O(n)$.

The rest of this section is devoted to proving the following:

${\mbox{\sf F}}^{k-1}(S_k) = \Omega(\frac{n}{k} \log (n/k))$

Let $T$ be an arbitrary reference tree. We argue that ${\mbox{\sf F}}^{k-1}_T(S_k) = \Omega(\frac{n}{k} \log (n/k))$.

A [*finger configuration*]{} $\vec{f} = (f(1),\ldots, f(k-1)) \in [n]^{k-1}$ specifies to which keys the fingers are currently pointing. Any finger strategy can be described by a sequence $\vec{f}_1,\ldots, \vec{f}_n$, where $\vec{f}_t$ is the configuration after element $s_t$ is accessed. As before, we assume w.l.o.g. the following lazy update strategy:

\[prop:k-server\] For each time $t$, the configurations $\vec{f}_t$ and $\vec{f}_{t+1}$ differ at exactly one position. In other words, we only move the finger that is used to access $s_{t+1}$.

We view the input sequence $S_k$ as having $\ell$ phases: The first phase contains the subsequence $1, \ell+1,\ldots, \ell(k-1)+1$, and so on. Each phase is a subsequence of length $k$ that accesses keys starting in block $
bset_1$ and so on, until the block ${{\mathcal{B}}}_k$.

For each phase $p \in \{1,\ldots, \ell \}$, there is a time [$t \in [(p-1)k + 1, p \cdot k]$]{} such that $s_t$ is accessed by finger $j$ such that $f_{t-1}(j) $ and $f_t(j)$ are in different blocks, and $f_{t-1}(j) < f_t(j)$. That is, this finger moves to the block ${{\mathcal{B}}}_{b}$, $b = t \mod k$, from some block ${{\mathcal{B}}}_{b'}$, where $b' < b$, in order to serve $s_t$.

Consider the accesses in blocks ${{\mathcal{B}}}_1$, …, ${{\mathcal{B}}}_k$ in order. After the access in ${{\mathcal{B}}}_1$, we have a finger in ${{\mathcal{B}}}_1$ and hence at most $k - 2$ fingers in blocks ${{\mathcal{B}}}_2$, …, ${{\mathcal{B}}}_k$. If the access to ${{\mathcal{B}}}_2$ is served by a finger being in block ${{\mathcal{B}}}_1$ before the acces, we are done. Otherwise, it is server by a finger being in blocks ${{\mathcal{B}}}_{\ge 2}$ before the access. Then we have two fingers in blocks ${{\mathcal{B}}}_{\le 2}$ after the access and at most $k-3$ fingers in blocks ${{\mathcal{B}}}_{\ge 3}$. Continuing in this way, we will find the desired access.

For each phase $p \in [\ell]$, let $t_p$ denote the time for which such a finger moves across the blocks from left to right; if they move more than once, we choose $t_p$ arbitrarily. Let $J = \{t_p\}_{p=1}^{\ell}$. For each finger $j \in [k-1]$, each block $i \in [k]$ and block $i' \in [k]: i < i'$, let $J(j,i,i')$ be the set containing the time $t$ for which finger $f(j)$ is moved from block ${{\mathcal{B}}}_i$ to block ${{\mathcal{B}}}_{i'}$ to access $s_t$. Let $c(j,i,i') = |J(j,i,i')|$. Notice that $\sum_{j,i,i'} c(j,i,i') = \frac{n}{k} = \ell$, due to the lemma. Let $P(j,i,i')$ denote the phases $p$ for which $t_p \in J(j,i,i')$.

$\sum_{j, i, i': c(j,i,i') \geq 16} c(j,i,i') \geq n/2k$ if $n = \Omega(k^4)$.

There are only at most $k^3$ triples $(j,i,i')$, so the terms for which $c(j,i,i') < 16$ contribute to the sum at most $16k^3$. This means that the sum of the remaining is at least $n/k - 16k^3 \geq n/2k$ if $n$ satisfies $n= \Omega(k^4)$.

From now on, we consider the sets $J'$ and $J'(j,i,i')$ that only concern those $c(j,i,i')$ with $c(j,i,i') \geq 16$ instead.

\[lem:key-lemma\] There is a constant $\eta >0$ such that the total access cost during the phases $P(j,i,i')$ is at least $\eta c(j,i,i') \log c(j,i,i')$.

Once we have this lemma, everything is done. Since the function $g(x) = x \log x$ is convex, we apply Jensen’s inequality to obtain: $$\frac{1}{|J'|} \sum_{j,i,i'} \eta c(j,i,i')\log c(j,i,i') \geq \eta \cdot \frac{n}{2k|J'|} \cdot \log (n/2k|J'|).$$ Note that the left side is the term ${\mathbb E}[g(x)]$, while the right side is $g({\mathbb E}(x))$. Therefore, the total access cost is at least $\frac{\eta n}{8k} \log (n/2k)$. We now prove the lemma.

We recall that, in the phases $P(j,i,i')$, the finger-$j$ moves from block ${{\mathcal{B}}}_i$ to ${{\mathcal{B}}}_{i'}$ to serve the request at corresponding time. For simplicity of notation, we use $\tilde J$ and $C$ to denote $J(j,i,i')$ and $c(j,i,i')$ respectively. Also, we use $\tilde f$ to denote the finger-$j$. For each $t \in \tilde J$, let $a_t \in {{\mathcal{B}}}_i$ be the key for which the finger $\tilde f$ moves from $a_t$ to $s_t$ when accessing $s_t \in {{\mathcal{B}}}_{i'}$. Let $\tilde J = \{t_1,\ldots, t_{C}\}$ such that $a_{t_1} < a_{t_2} <  \ldots < a_{t_{C}}$. Let $R$ be the lowest common ancestor in $T$ of keys in $[a_{t_{\lfloor C/2 \rfloor } +1}, a_{t_{C}}]$.

\[lem:lastclaim\] For each $r \in \{1,\ldots, \lfloor C/2 \rfloor \}$, the access cost of $s_{t_r}$ and $s_{t_{C -r}}$ is together at least $\min \{d_T({R}, s_{t_r}), d_T(R, s_{t_{C -r}})\}$.

Let $u_r$ be the lowest common ancestor between $a_{t_r}$ and $s_{t_r}$. Then the cost of accessing $s_{t_r}$ is at least $d_T(u_r,s_{t_r})$. If $s_{t_r}$ is in the subtree rooted at $R$, then $u_r$ must be an ancestor of $R$ (because $a_{t_r} < a_{t_{\lfloor C/2 \rfloor }} < a_{t_{C}} < s_{t_r}$) and hence $d_T(u_r, s_{t_r}) \geq d_T(R,s_{t_r})$. Thus the cost it at least $d_T(R,s_{t_r})$. Otherwise, we know that $s_{t_r}$ is outside of the subtree rooted at $R$, and so is $s_{t_{C- r}}$. On the other hand, $a_{t_{C-r}}$ is in such subtree, so moving the finger from $a_{t_{C -r}}$ to $s_{t_{C - r}}$ must touch ${R}$, therefore costing at least $d_T({R}, s_{t_{C-r}})$.

Lemma \[lem:lastclaim\] implies that, for each $r=1,\ldots, \lfloor C/2 \rfloor $, we pay the distance between some element $v_r \in {\left\{ s_{t_r}, s_{t_{C-r}} \right\}}$ to $R$. The total such costs would be $\sum_{r} d_T(R, v_r)$. Applying the fact that (i) $v_r$’s are different and (ii) there are at most $3^d$ vertices at distance $d$ from a vertex $R$, we conclude that this sum is at least $\sum_r d_T(R, v_r) \geq \Omega(C \log C)$.

Working set and $k$-finger bounds are incomparable
==================================================

We show the following theorem.

\[sec:WS-LF\]

(1) There exists a sequence $S$ such that ${\mbox{\sf WS}}(S) = o({\mbox{\sf F}}^{k}(S))$, and

(2) There exists a sequence $S^{'}$ such that ${\mbox{\sf F}}^{k}(S^{'}) = o({\mbox{\sf WS}}(S^{'}))$.

The sequence $S^{'}$ above is straightforward: For $k=1$, just consider the sequential access $1,\dots,n$ repeated $m/n$ times. For $m$ large enough, the working set bound is $\Omega(m \log n)$. However, if we start with the finger on the root of the tree which is just a path, then the lazy finger bound is $O(m)$. The $k$-finger bound is always less than lazy finger bound, so this sequence works for the second part of the theorem.

The existence of the sequence $S$ is slightly more involved (the special case for $k=1$ was proved in [@BoseDIL14]), and is guaranteed by the following theorem, the proof of which comprises the remainder of this section.

\[wslessklf\] For all $k = O(n^{1/2 - \epsilon})$, there exists a sequence $S$ of length $m$ such that ${\mbox{\sf WS}}(S) = O(m \log k)$ whereas $F^{k}(S) = \Omega(m \log (n/k))$.

We construct a random sequence $S$ and show that while ${\mbox{\sf WS}}(S) = O(m \log k)$ with probability one, the probability that there exists a tree ${{\mathcal T}}$ such that ${\mbox{\sf F}}^{k}_{T}(S) \leq c m\log_{3} (n/k)$ is less than $1/2$ for some constant $c<1$. This implies the existence of a sequence $S$ such that for all trees ${{\mathcal T}}$, ${\mbox{\sf F}}^{k}_{T}(S) = \Omega(m \log (n/k))$.

The sequence is as follows. We have $Y$ phases. In each phase we select $2k$ elements $R_{i} = \{r^{i}_{j}\}_{j=1}^{2k}$ uniformly at random from $[n]$. We order them arbitrarily in a sequence $S_{i}$, and access $[S_{i}]^{X/2k}$ (access $S_{i}$ $X/2k$ times). The final sequence $S$ is a concatenation of the sequences $[S_{i}]^{X/2k}$ for $1 \leq i \leq Y$. Each phase has $X$ accesses, for a total of $m= XY$ accesses overall. We will choose $X$ and $Y$ appropriately later.

##### **Working set bound.** {#working-set-bound. .unnumbered}

One easily observes that ${\mbox{\sf WS}}(S) =O(Y(2k \log n + (X-2k) \log (2k)))$, because after the first $2k$ accesses in a phase, the working set is always of size $2k$. We choose $X$ such that the second term dominates the first, say $X \geq 5 k \frac{\log n}{\log 2k}$. We then have that the working set bound is $O(XY \log k) = O(m \log k)$, with probability one.

##### **$k$-finger bound.** {#k-finger-bound. .unnumbered}

Fix a BST ${{\mathcal T}}$. We classify the selection of the set $R_{i}$ as being $d$-good for ${{\mathcal T}}$ if there exists a pair $r^{i}_{j}, r^{i}_{\ell} \in R_{i}$ such that their distance in ${{\mathcal T}}$ is less than $d$. The following lemma bounds the probability of a random selection being $d$-good for ${{\mathcal T}}$.

Let ${{\mathcal T}}$ be any BST. The probability that $R_{i}$ is $d$-good for ${{\mathcal T}}$ is at most $8k^{2}3^{d}/n$.

We may assume $8 k^2 3^d/n < 1$ as the claim is void otherwise. We compute the probability that a selection $R_{i}$ is not $d$-good first. This happens if and only if the balls of radius $d$ around every element $r^{i}_{j}$ are disjoint. The volume of such a ball is at most $3^d$, so we can bound this probability as

$$\begin{aligned}
P[R_{i}\text{ is not d-good for }{{\mathcal T}}] &=& \displaystyle\Pi_{i=1}^{2k-1} \left(1-\frac{i3^d}{n}\right) \notag \\
                                &\geq& \left( 1-\frac{2k3^d}{n}\right)^{2k} \notag \\
\Rightarrow P[R_{i}\text{ is d-good for }{{\mathcal T}}] &\leq& 1- \left( 1-\frac{2k3^d}{n}\right)^{2k} \notag \\
                                    &=& 1- \exp\left(2k \ln \left( 1-\frac{2k3^d}{n}\right)\right) \notag \\
                                    &\leq& 1 - \exp\left(-8k^{2}3^{d}/n\right) \notag \\
                                    &\leq& 8k^{2}3^{d}/n, \notag\end{aligned}$$

where the last two inequalities follow from $\ln (1-x) > -2x$ for $x \le 1/2$ (note that $8 k^2 3^d/n < 1$ implies $2k 3^d/n \le 1/2$) and $e^x > 1+x$, respectively.

Observe that if $R_{i}$ is not $d$-good, then the $k$-finger bound of the access sequence $[S_{i}]^{X/2k}$ is $\Omega(d(X-k))=\Omega(dX)$. This is because in every occurrence of $S_{i}$, there will be some $k$ elements out of the $2k$ total that will be outside the $d$-radius balls centered at the current $k$ fingers.

We call the entire sequence $S$ $d$-good for ${{\mathcal T}}$ if at least half of the sets $R_{i}$ are $d$-good for ${{\mathcal T}}$. Thus if $S$ is not $d$-good, then ${\mbox{\sf F}}^{k}_{{{\mathcal T}}}(S) = \Omega(XYd)$.

$P[S\text{ is d-good for }{{\mathcal T}}] \leq \left(\frac{32k^{2}3^{d}}{n} \right)^{Y/2}$.

By the previous lemma and by definition of goodness of $S$, we have that

$$\begin{aligned}
P[S\text{ is d-good for }{{\mathcal T}}] \leq {Y \choose Y/2}\left(\frac{8k^{2}3^{d}}{n} \right)^{Y/2} 
             \leq 4^{Y/2}\left(\frac{8k^{2}3^{d}}{n} \right)^{Y/2} 
            = \left(\frac{32k^{2}3^{d}}{n} \right)^{Y/2}.\end{aligned}$$

The theorem now follows easily. Taking a union bound over all BSTs on $[n]$, we have $$P[S\text{ is d-good for some BST }{{\mathcal T}}] \leq 4^{n}\left(\frac{32k^{2}3^{d}}{n} \right)^{Y/2}.$$ Now set $Y=2n$. We have that $$P[\exists \text{ a BST }{{\mathcal T}}:{\mbox{\sf F}}^{k}_{{{\mathcal T}}}(S) \leq md/4] \leq 4^{n}\left(\frac{32k^{2}3^{d}}{n} \right)^{n}.$$ Putting $d = \log_{3} \frac{n}{256k^{2}}$ gives that for some constant $c<1$, $$P[\exists \text{ a BST }{{\mathcal T}}:{\mbox{\sf F}}^{k}_{{{\mathcal T}}}(S) \leq c(m \log (n/k))] \leq 4^{n}\left(\frac{32k^{2}3^{d}}{n} \right)^{n} = 1/2$$ which implies that with probability at least $1/2$ one of the sequences in our random construction will have $k$-finger bound that is $\Omega(m \log (n/k))$. The working set bound is always $O(m \log k)$. This establishes the theorem.

[^1]: To simplify notation, we let $\log{(x)}$ denote $\log_2{(\max\{2,x\})}$.

[^2]: The initial 1977 design of Guibas et al. [@guibas] was refined and simplified by Brown and Tarjan [@BrownTarjan] and by Huddleston and Mehlhorn [@Huddleston]. Further solutions include [@Tsakalidis; @TarjanWyk; @Kosaraju; @KaplanTarjan], see also the survey [@BrodalSurvey]. Randomized treaps [@SeidelA96] and skip lists [@SkipList] can also support finger search.

[^3]: Greedy BST was discovered by Lucas in 1988 [@Luc88] and later independently by Munro [@Mun00]. Demaine et al. [@DHIKP09] transformed it into an online algorithm.

[^4]: An *online* BST algorithm can base its decisions only on the current and past accesses. An *offline* algorithm knowns the entire access sequence in advance.

[^5]: To avoid technicalities, we only consider *access* (i.e. successful search) operations and assume $m \geq n$.

[^6]: Another attempt to study the bounds related to the unified bound was done in [@fresh-finger].

[^7]: The proof of Theorem \[thm: weak UB\] implies in fact a stronger, *weighted* form, which we omit for ease of presentation.

[^8]: Independently of our work, Goyal and Gupta [@goyalgupta] showed the same result using a charging argument.

[^9]: In his work on a generalized $k$-server problem, Sitters [@Sitters] asks whether the work-function (WF) technique [@Koutsoupias] for $k$-server may have relevance for BSTs. Indeed, we can use WF as an $O(k)$-competitive component of our online BSTs, but for our special case of tree-metrics, the technique of [@chrobak] is much simpler. Whether WF may be used (in different ways) to obtain competitive BSTs remains open.

[^10]: We let $x_0$ denote the root of $T$, and distances involving negative indices are defined to be $+\infty$.

[^11]: The result holds, in fact, for the more general case, when each $X_i$ is either increasing or decreasing.

[^12]: In [@CombineBST], the hand is defined only over the pseudofingers.
