## 1 Introduction
[17; 18; 19]. It avoids the explicit representation of the tree topology by working all the time with the corresponding suffix array intervals. All the suffix tree navigation is reduced to three primitive operations on such intervals: Next/Previous smaller value and range minimum queries (more details later). The proposal achieves a space/time tradeoff that is between the two previous ones: It reduces the \(\Theta(n)\) extra bits of Sadakane to \(o(n)\), and the superlogarithmic operation times of [PERSON] _et al_. to \(O(\log^{\epsilon}n)\), for any constant \(0<\epsilon<1\). More precisely, the space is \(nH_{k}(2\max(1,\log(1/H_{k}))+1/\epsilon+O(1))+o(n\log\sigma)\) bits (for the same \(k\) ranges as above). We remark that the space figures include the storage of the sequence itself, as all modern CSA are _self-indexes_, that is, they contain both the sequence and its suffix array. For applications, the _practical_ performance of the above schemes is more relevant than the theoretical figures. The solution based on explicit topology was implemented by [PERSON] _et al_. [20]. As expected from theory, the structure is very fast, achieving a few tens of microseconds per operation, but uses significant space (about 25-35 bpc, close to a suffix array). This undermines its applicability. Very recently, [PERSON] [21] showed that this implementation can be made much more space-efficient, using about 13-17 bpc. This still puts this solution in the range of the \"large\" CSTs in the context of this paper. The structure based on sampling was implemented by [PERSON]. As expected from theory again, it was shown to achieve very little space, around 4-6 bpc, which makes it extremely attractive when the sequence is large compared with the available main memory. On the other hand, the structure is much slower than the previous one: Each navigation operation takes the order of milliseconds. In this paper we present the _first_ implementations of the third approach, based on intervals. As predicted by theory once again, we achieve practical implementations that lie between the two previous extremes (too large or too slow) and offer attractive space/time tradeoffs. One variant shows to be superior to the original implementation of [PERSON]'s CST [20] in both space and time: It uses 13-16 bpc (_i.e._, half the space) and requires a few microseconds per operation (_i.e._, several times faster). A second variant works within 8-12 bpc and requires a few hundreds of microseconds per operation, that is, smaller than our first variant and still several times faster than [PERSON]'s implementation. We remark again that those space figures include the storage of the sequence, and that 8 bpc is the storage space of a byte-based representation of the plain sequence (although 2 bpc is easily achieved on DNA). Achieving those good practical results is not immediate, however. We show that a direct implementation of the techniques as described in the theoretical proposal [18] does not lead to the best performance. Instead, we propose a novel solution to the previous/next smaller value and range minimum queries, based on the _range min-max tree_ (_RMM tree_), a recent data structure developed for succinct tree representations [22, 23]. We adapt RMM trees to speed up the desired queries on sequences of LCP values. The resulting representation not only performs better than a verbatim implementation of the theoretical proposal, but also has a great potential to handle _highly repetitive_ sequence collections. Those collections, formed by many similar strings, arise in version control systems, periodic publications, and software repositories. They also arise naturally in bioinformatics, for example when sequencing the genomes of many individuals of the same or related species (two human genomes share 99.9% of their sequences, for example). It is likely that the largest genome collections that will emerge in the next years will be highly repetitive, and taking advantage of that repetitiveness will be the key to handle them.