Na záver si ešte ukážeme jeden trik, ktorý sa dá pomocou treapov robiť. Vieme si pomocou nich vyrobiť dátovú štruktúru, ktorá sa bude podobať na obyčajné pole. Prístup ku konkrétnemu prvku, teda operátor [], bude potrebovať až logaritmický čas. Zato ale budeme vedieť efektívne robiť omnoho viac operácií ako s obyčajným poľom:
Hlavná myšlienka bude nasledovná: Budeme mať dáta, teda v každom vrchole stromu bude uložený údaj, ktorý by bol uložený na jednom políčku obyčajného poľa. Budeme mať aj priority, používané budú presne rovnako ako vo vyššie popísanej implementácii. Vôbec však nebudeme mať kľúče. Namiesto toho sa budeme tváriť, že pre každý prvok platí, že jeho aktuálnym kľúčom je index, na ktorom by ležal v usporiadanom poli. (Inými slovami, jeho index v in-order zápise aktuálneho treapu.)
Kľúče si nikdy nebudeme nikam ukladať. To by ani nefungovalo — akonáhle by sme pridali nejaký nový prvok do stredu, museli by sme prečíslovať všetky vrcholy napravo od neho. Namiesto toho si kľúče budeme priebežne počítať počas operácií s treapom.
Toto počítanie bude veľmi jednoduché. Keď sme v koreni, vieme, že jeho aktuálny kľúč je rovný počtu vrcholov v jeho ľavom podstrome. A ako schádzame dole stromom, vieme si priebežne pamätať, koľko existuje v našom treape vrcholov menších od aktuálneho, a teda od akého kľúča začínajú prvky v jeho podstrome. Inými slovami, robíme presne to isté, ako vo vyššie popísanej metóde kth_smallest.
Metóda merge sa vôbec nezmení, keďže tá sa na kľúče nepotrebovala pozerať. Ukážeme si teraz novú implementáciu metódy split.
// pribudol parameter add hovoriaci, že prvky v podstrome s koreňom t začínajú od indexu add
void split(pitem t, T key, pitem &l, pitem &r, int add = 0) {
if (!t) { l = r = NULL; return; }
int t_key = add + get_size(t->l); // vypočítame implicitne určený kľúč pre vrchol t
if (key < t->key) {
split(t->l, key, l, t->l, add);
r = t;
} else {
split(t->r, key, t->r, r, add + 1 + get_size(t->l));
l = t;
}
}
Vloženie nového prvku sa dá spraviť tak, že na vhodnom mieste spravíme split aktuálneho treapu na $T_1$ obsahujúci prvky, ktoré majú byť naľavo od vkladaného a $T_2$ obsahujúci prvky, ktoré majú byť napravo od neho. Potom spravíme jednoprvkový $T_3$ obsahujúci vkladaný prvok a spravíme merge(merge(T1,T3),T2).
Vymazanie prvku je ešte ľahšie. Nájdeme prvok, ktorý chceme vymazať, zmažeme ho a "dieru po ňom" zaplátame jednoducho tak, že spravíme merge jeho oboch podstromov.
Operácie na intervaloch sa robia tak, že v každom vrchole pribudnú nové premenné, obsahujúce informáciu o jeho podstrome. Vždy, keď vrchol navštívime a nejak zmeníme, vieme túto informáciu prepočítať z jeho synov. (Napr. minimum pre môj podstrom viem určiť z miním pre podstromy mojich synov a z hodnoty, ktorá je v mojom vrchole.) Operácie potom robíme tak, že pomocou dvoch splitov odizolujeme interval, ktorý nás zaujíma, pozrieme sa do jeho koreňa (resp. tam niečo zapíšeme) a následne všetko mergeneme naspäť do jedného stromu.