*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 