Arbori_de_intervale

ARBORI DE INTERVALE

Un arbore de intervale este o structură de date care permite să răspundă în mod eficient la interogări de gamă pe o vectorul, fiind totuși suficient de flexibil pentru a permite modificarea vectorului. Aceasta include găsirea sumei elementelor de vectorul consecutive a [l ... r] sau găsirea elementului minim într-un astfel de interval în timpul O (logn). Între răspunsul la astfel de întrebări, Arborele intervalului permite modificarea vectorului prin înlocuirea unui element sau chiar schimbarea elementelor unui întreg interval (de exemplu, atribuirea tuturor elementelor a [l ... r] la orice valoare sau adăugarea unei valori tuturor elementelor din intervalul secundar ).
În general, un arbore de intervale este o structură de date foarte flexibilă și un număr mare de probleme pot fi rezolvate cu acesta. În plus, este, de asemenea, posibil să aplicați operațiuni mai complexe și să răspundeți la interogări mai complexe (consultați versiunile avansate ale arborilor de interval). În special Arborele intervalului poate fi ușor generalizat la dimensiuni mai mari. De exemplu, cu un arbore de intervale bidimensional, puteți răspunde la întrebări sumare sau minime pentru un subrectangul al unei vectorul date. Cu toate acestea, numai în timp O (log2n).

O proprietate importantă a arborilor de intervale este aceea că necesită doar o cantitate liniară de memorie. Arborele intervalului standard necesită 4*n vârfuri pentru a lucra la un vector de dimensiunea n.
Cea mai simplă formă de arbore de intervale
Pentru a începe ușor, considerăm cea mai simplă formă de arbore de intervale. Vrem să răspundem eficient la întrebările de sumă. Definiția formală a sarcinii noastre este: Avem o vectorul a [0… n − 1], iar Arborele Intervalului trebuie să fie capabil să găsească suma elementelor dintre indicii l și r (adică calculând suma ∑ri = la [ i]), și, de asemenea, se ocupă de schimbarea valorilor elementelor din vectorul (adică efectuați atribuții ale formei a [i] = x). Arborele intervalului ar trebui să poată procesa ambele interogări în timp O (logn).

Structura arborelui intervalului
Deci, ce este un arbore de intervale?

Calculăm și stocăm suma elementelor întregului tablou, adică suma intervalului a [0 ... n − 1]. Apoi împărțim vectorul în două jumătăți a [0 ... n / 2] și a [n / 2 + 1 ... n − 1] și calculăm suma fiecărei jumătăți și le stocăm. La rândul lor, fiecare dintre aceste două jumătăți se împarte la jumătate, sumele lor sunt calculate și stocate. Și acest proces se repetă până când toate intervalele ating dimensiunea 1. Cu alte cuvinte, începem cu intervalul a [0 ... n − 1], împărțim intervalul curent în jumătate (dacă nu a devenit încă un interval care conține un singur element) și apelând apoi aceeași procedură pentru ambele jumătăți. Pentru fiecare astfel de interval stocăm suma numerelor de pe acesta.

Putem spune că aceste intervale formează un arbore binar: rădăcina acestui arbore este intervalul a [0 ... n − 1] și fiecare vârf (cu excepția vârfurilor frunzelor) are exact două vârfuri copil. Acesta este motivul pentru care structura datelor este numită „Arborele intervalului”, chiar dacă în majoritatea implementărilor arborele nu este construit în mod explicit (vezi Implementare).

Iată o reprezentare vizuală a unui astfel de arbore de intervale peste tabloul a = [1,3, −2,8, −7]:






















Din această scurtă descriere a structurii datelor, putem concluziona deja că un arbore de intervale necesită doar un număr liniar de vârfuri. Primul nivel al arborelui conține un singur nod (rădăcina), al doilea nivel va conține două vârfuri, în al treilea va conține patru vârfuri, până când numărul de vârfuri ajunge la n. Astfel, numărul de vârfuri în cel mai rău caz poate fi estimat prin suma 1 + 2 + 4 + ⋯ + 2⌈log2n⌉ = 2⌈log2n⌉ + 1 <4*n.

Este demn de remarcat faptul că ori de câte ori n nu este o putere de două, nu toate nivelurile din Arborele Intervalului vor fi complet umplute. Putem vedea acest comportament în imagine. Deocamdată putem uita de acest fapt, dar va deveni important mai târziu în timpul implementării.

Înălțimea arborelui intervalului este O (logn), deoarece atunci când coborâți de la rădăcină la frunze, dimensiunea intervalelor scade aproximativ la jumătate.
Constructie
Înainte de a construi arborele intervalului, trebuie să decidem:

1.	valoarea care este stocată la fiecare nod al arborelui intervalului. De exemplu, într-un arbore de interval de sumă, un nod ar stoca suma elementelor din intervalul său [l, r].
2.	operațiunea de îmbinare care fuzionează doi frați într-un arbore de intervale. De exemplu, într-un arbore de intervale de sumă, cele două noduri corespunzătoare intervalelor a [l1 ... r1] și a [l2 ... r2] ar fi îmbinate într-un nod corespunzător intervalului a [l1 ... r2] prin adăugarea valorilor de cele două noduri.
Rețineți că un vârf este un „vârf de frunză”, dacă intervalul său corespunzător acoperă o singură valoare din vectorul originală. Este prezent la nivelul cel mai de jos al unui arbore interval. Valoarea sa ar fi egală cu elementul (corespunzător) a [i].

Acum, pentru construcția arborelui intervalului, începem de la nivelul inferior (vârfurile frunzelor) și le atribuim valorile respective. Pe baza acestor valori, putem calcula valorile nivelului anterior, utilizând funcția de îmbinare. Și pe baza acestora, putem calcula valorile precedentului și putem repeta procedura până când ajungem la vârful rădăcinii.

Este convenabil să descrieți această operațiune recursiv în cealaltă direcție, adică de la vârful rădăcinii până la vârfurile frunzelor. Procedura de construcție, dacă este apelată pe un vârf fără frunze, face următoarele:

1.	construiți recursiv valorile celor două vârfuri copil
2.	îmbinați valorile calculate ale acestor copii.
Începem construcția la vârful rădăcinii și, prin urmare, suntem capabili să calculăm întregul arbore de intervale.

Complexitatea de timp a acestei construcții este O (n), presupunând că operația de îmbinare este un timp constant (operația de îmbinare este numită de n ori, care este egal cu numărul de noduri interne din arborele intervalului).
 Sum Queries
Deocamdată vom răspunde la întrebări de sumă. Ca intrare primim două numere întregi l și r și trebuie să calculăm suma intervalului a [l ... r] în timpul O (logn).

Pentru a face acest lucru, vom traversa Arborele Intervalului și vom utiliza sumele precomputate ale intervalelor. Să presupunem că suntem în prezent la vârful care acoperă intervalul a [tl ... tr]. Există trei cazuri posibile:

Cel mai ușor caz este când intervalul a [l ... r] este egal cu intervalul corespunzător al vârfului curent (adică a [l ... r] = a [tl ... tr]), atunci am terminat și putem returna suma precomputată care este stocat în vârf.
Alternativ, intervalul interogării poate intra complet în domeniul copilului din stânga sau din cel din dreapta. Amintiți-vă că copilul din stânga acoperă intervalul a [tl ... tm] și vârful drept acoperă intervalul a [tm + 1 ... tr] cu tm = (tl + tr) / 2. În acest caz, putem merge pur și simplu la vârful copil, care interval corespunzător acoperă intervalul de interogare și executăm algoritmul descris aici cu acel vârf.
Și apoi este ultimul caz, intervalul de interogare se intersectează cu ambii copii. În acest caz, nu avem altă opțiune ca să efectuăm două apeluri recursive, unul pentru fiecare copil. Mai întâi mergem la copilul din stânga, calculăm un răspuns parțial pentru acest vârf (adică suma valorilor intersecției dintre intervalul interogării și intervalul copilului din stânga), apoi mergem la copilul din dreapta, calculăm răspunsul parțial folosind acel vârf și apoi combinați răspunsurile adăugându-le. Cu alte cuvinte, deoarece copilul din stânga reprezintă intervalul a [tl ... tm] și copilul din dreapta intervalul a [tm + 1 ... tr], calculăm interogarea sumă a [l ... tm] folosind copilul din stânga și suma interogării a [tm + 1 ... r] folosind copilul potrivit.

Prin urmare, procesarea unei interogări sumare este o funcție care se numește recursiv o dată fie cu stânga, fie cu copilul drept (fără a modifica limitele interogării), sau de două ori, o dată pentru stânga și o dată pentru copilul drept (prin împărțirea interogării în două subinterogări ). Și recursivitatea se termină ori de câte ori limitele intervalului de interogare curent coincid cu limitele intervalului vârfului curent. În acest caz, răspunsul va fi valoarea precomputată a sumei acestui interval, care este stocată în arbore.

Cu alte cuvinte, calculul interogării este o traversare a arborelui, care se răspândește prin toate ramurile necesare ale arborelui și utilizează valorile sumelor precomputate ale intervalelor din arbore.

Evident, vom începe traversarea de la vârful rădăcinii Arborelui intervalului.

Procedura este ilustrată în următoarea imagine. Din nou se folosește vectorul a = [1,3, −2,8, −7] și aici vrem să calculăm suma ∑4i = 2a [i]. Vârfurile colorate vor fi vizitate și vom folosi valorile precomputate ale vârfurilor verzi. Acest lucru ne dă rezultatul −2 + 1 = −1.























De ce este complexitatea acestui algoritm O (logn)? Pentru a arăta această complexitate, ne uităm la fiecare nivel al arborelui. Se pare că pentru fiecare nivel vizităm nu mai mult de patru vârfuri. Și întrucât înălțimea copacului este O (logn), primim timpul de funcționare dorit.

Putem arăta că această propoziție (cel mult patru vârfuri fiecare nivel) este adevărată prin inducție. La primul nivel, vizităm doar un vârf, vârful rădăcinii, așa că aici vizităm mai puțin de patru vârfuri. Acum să ne uităm la un nivel arbitrar. Prin ipoteza inducției, vizităm cel mult patru vârfuri. Dacă vizităm doar cel mult două vârfuri, nivelul următor are cel mult patru vârfuri. Acest lucru banal, deoarece fiecare vârf poate provoca cel mult două apeluri recursive. Deci, să presupunem că vizităm trei sau patru vârfuri în nivelul curent. Din acele vârfuri, vom analiza vârfurile din mijloc mai atent. Deoarece interogarea sumă solicită suma unui subarray continuu, știm că intervalele corespunzătoare vârfurilor vizitate din mijloc vor fi acoperite complet de intervalul interogării sumelor. Prin urmare, aceste vârfuri nu vor efectua apeluri recursive. Deci, doar cel mai stâng și cel mai drept vârf vor avea potențialul de a efectua apeluri recursive. Și acestea vor crea doar cel mult patru apeluri recursive, astfel încât și nivelul următor va satisface afirmația. Putem spune că o ramură se apropie de limita stângă a interogării, iar a doua ramură se apropie de dreapta.

Prin urmare, vizităm cel mult 4 vârfuri în total, iar acest lucru este egal cu un timp de rulare de O (logn).

În concluzie, interogarea funcționează prin împărțirea intervalului de intrare în mai multe sub-intervale pentru care toate sumele sunt deja precomputate și stocate în arborele. Și dacă oprim partiționarea ori de câte ori intervalul de interogare coincide cu intervalul de vârf, atunci avem nevoie doar de O (logn) astfel de intervale, ceea ce oferă eficiența Arborelui intervalului.

Actualizați interogările
Acum vrem să modificăm un anumit element din vectorul, să presupunem că vrem să facem atribuția a [i] = x. Și trebuie să reconstruim Arborele Intervalului, astfel încât să corespundă noii vectorul modificate.
Această interogare este mai ușoară decât interogarea sumă. Fiecare nivel al unui arbore de intervale formează o partiție a vectorului. Prin urmare, un element a [i] contribuie doar la un interval din fiecare nivel. Astfel, numai vârfurile O (logn) trebuie actualizate.
Este ușor de văzut că cererea de actualizare poate fi implementată utilizând o funcție recursivă. Funcția este trecută de vârful curent al arborelui și se numește recursiv cu unul dintre cele două vârfuri copil (cel care conține un [i] în intervalul său) și după aceea își recalculează valoarea sumă, similar modului în care se face în metoda build (adică suma celor doi copii ai săi).
Din nou, aici este o vizualizare folosind aceeași vectorul. Aici efectuăm actualizarea a [2] = 3. Vârfurile verzi sunt vârfurile pe care le vizităm și le actualizăm.























Implementare
Considerentul principal este modul de stocare a arborelui intervalului. Desigur, putem defini o structură Vertex și putem crea obiecte, care stochează limitele intervalului, suma acestuia și, de asemenea, indicatori către vârfurile copilului său. Cu toate acestea, acest lucru necesită stocarea multor informații redundante. Vom folosi un truc simplu, pentru a face acest lucru mult mai eficient. Stocăm sumele doar într-un vector. Suma vârfului rădăcinii la indexul 1, sumele celor două vârfuri ale sale la indicii 2 și 3, sumele copiilor celor doi vârfuri la indicii 4-7 și așa mai departe. Este ușor de văzut că copilul stâng al unui vârf la indexul i este stocat la indexul 2i, iar cel drept la indexul 2i + 1.
Acest lucru simplifică mult implementarea. Nu este nevoie să stocăm structura arborelui în memorie. Este definit implicit. Avem nevoie doar de o vectorul care conține sumele tuturor intervalelor.
După cum sa menționat anterior, trebuie să stocăm cel mult 4n vârfuri. Ar putea fi mai puțin, dar pentru comoditate alocăm întotdeauna o serie de dimensiuni 4n. Vor exista unele elemente în vectorul sumă, care nu vor corespunde niciunui vârf din arborele propriu-zis, dar acest lucru nu complică implementarea.

Deci, stocăm Arborele intervalului pur și simplu ca o vectorul t [] cu o dimensiune de patru ori mai mare decât dimensiunea de intrare n:
int n, t[4*MAXN];

Procedura pentru construirea Arborelui Intervalului dintr-un vector dat a [] arată astfel: este o funcție recursivă cu parametrii a [] (vectorul de intrare), v (indicele vârfului curent) și limitele tl și tr al intervalului curent. În programul principal, această funcție va fi apelată cu parametrii vârfului rădăcină: v = 1, tl = 0 și tr = n − 1.
void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = t[v*2] + t[v*2+1];
    }
}

În plus, funcția de răspuns la interogări de sumă este, de asemenea, o funcție recursivă, care primește ca parametri informații despre vârful / intervalul curent (adică indicele v și limitele tl și tr) și, de asemenea, informații despre limitele interogării, l și r . Pentru a simplifica codul, această funcție efectuează întotdeauna două apeluri recursive, chiar dacă este necesar doar unul - în acest caz apelul recursiv superflu va avea l> r, iar acest lucru poate fi ușor surprins folosind o verificare suplimentară la începutul funcţie.
int sum(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l == tl && r == tr) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return sum(v*2, tl, tm, l, min(r, tm))
           + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}
În cele din urmă, interogarea de actualizare. Funcția va primi, de asemenea, informații despre vârful / intervalul curent, precum și parametrul interogării de actualizare (adică poziția elementului și noua sa valoare).
void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = t[v*2] + t[v*2+1];    }      }
Implementarea eficientă a memoriei
Majoritatea oamenilor folosesc implementarea din secțiunea anterioară. Dacă vă uitați la vectorul t, puteți vedea că acesta urmează numerotarea nodurilor arborelui în ordinea unei traversări BFS (traversare de nivel de nivel). Folosind această traversare, copiii vârfului v sunt 2v și respectiv 2v + 1. Cu toate acestea, dacă n nu este o putere de două, această metodă va sări peste unii indici și va lăsa unele părți ale vectorului t neutilizate. Consumul de memorie este limitat de 4n, chiar dacă un arbore de intervale dintr-o vectorul de n elemente necesită doar 2n − 1 vârfuri.

Cu toate acestea, poate fi redus. Renumerotăm vârfurile arborelui în ordinea unei traversări de tur Euler (trecere pre-comandă) și scriem toate aceste vârfuri una lângă alta.

Să vedem un vârf la indexul v și să-l responsabilizăm pentru intervalul [l, r] și să lăsăm mid=(l+r)/2. Este evident că copilul din stânga va avea indicele v + 1. Copilul stâng este responsabil pentru intervalul [l, mid], adică în total vor exista 2 ∗ (mid − l + 1) −1 vârfuri în subarborele copilului stâng. Astfel putem calcula indicele copilului drept al lui v. Indicele va fi v + 2 ∗ (mijlocul − l + 1). Prin această numerotare realizăm o reducere a memoriei necesare la 2n.
Versiuni avansate de arbori de interval
Un arbore de intervale este o structură de date foarte flexibilă și permite variații și extensii în multe direcții diferite. Să încercăm să le clasificăm mai jos.

Interogări mai complexe
Poate fi destul de ușor să schimbați Arborele intervalului într-o direcție, astfel încât să calculeze interogări diferite (de exemplu, calculând minimul / maximul în loc de sumă), dar poate fi, de asemenea, foarte netivial.

Găsirea maximului
Să schimbăm ușor starea problemei descrise mai sus: în loc să interogăm suma, vom face acum întrebări maxime.
Arborele va avea exact aceeași structură ca arborele descris mai sus. Trebuie doar să schimbăm modul în care t [v] este calculat în funcțiile de construire și actualizare. t [v] va stoca acum maximul intervalului corespunzător. Și trebuie, de asemenea, să schimbăm calculul valorii returnate a funcției sumă (înlocuirea însumării cu maximul).
Desigur, această problemă poate fi ușor schimbată în calculul minimului în loc de maxim.
În loc să arate o implementare pentru această problemă, implementarea va fi dată unei versiuni mai complexe a acestei probleme în secțiunea următoare.
Găsirea maximului și a numărului de apariții
Această sarcină este foarte asemănătoare cu cea anterioară. Pe lângă găsirea maximului, trebuie să găsim și numărul de apariții ale maximului.
Pentru a rezolva această problemă, stocăm o pereche de numere la fiecare vârf din arbore: Pe lângă maxim, stocăm și numărul de apariții al acesteia în intervalul corespunzător. Determinarea perechii corecte de stocat la t [v] se poate face în timp constant folosind informațiile perechilor stocate la vârfurile copilului. Combinarea a două astfel de perechi ar trebui să se facă într-o funcție separată, deoarece aceasta va fi o operație pe care o vom face în timp ce construim arborele, în timp ce răspundem la întrebări maxime și în timp ce efectuăm modificări.

pair<int, int> t[4*MAXN];

pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
    if (a.first > b.first)
        return a;
    if (b.first > a.first)
        return b;
    return make_pair(a.first, a.second + b.second);
}

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = make_pair(a[tl], 1);
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

pair<int, int> get_max(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return make_pair(-INF, 0);
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return combine(get_max(v*2, tl, tm, l, min(r, tm)),
                   get_max(v*2+1, tm+1, tr, max(l, tm+1), r));
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = make_pair(new_val, 1);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

Calculați cel mai mare divizor comun / cel mai mic multiplu comun
În această problemă vrem să calculăm GCD / LCM pentru toate numerele de intervale date ale vectorului.

Această variație interesantă a Arborelui Intervalului poate fi rezolvată exact în același mod ca și Arborii Intervalului pe care i-am derivat pentru interogări sumă / minimă / maximă: este suficient să stocați GCD / LCM al vârfului corespunzător în fiecare vârf al arborelui. Combinarea a două vârfuri se poate face prin calcularea GCM / LCM a ambelor vârfuri.

Numărarea numărului de zerouri, căutarea celui de-al zecelea zero
În această problemă vrem să găsim numărul de zerouri dintr-un interval dat și, în plus, să găsim indicele k-al zero folosind o a doua funcție.

Din nou, trebuie să schimbăm puțin valorile de stocare ale arborelui: De data aceasta vom stoca numărul de zerouri din fiecare interval în t []. Este destul de clar, cum să implementăm funcțiile de compilare, actualizare și count_zero, putem folosi pur și simplu ideile din problema interogării sumelor. Astfel am rezolvat prima parte a problemei.

Acum învățăm cum să rezolvăm problema găsirii k-a zero în vectorul a []. Pentru a face această sarcină, vom coborî Arborele Intervalului, începând de la vârful rădăcinii și deplasându-ne de fiecare dată fie la stânga, fie la copilul din dreapta, în funcție de intervalul care conține k-th zero. Pentru a decide la ce copil trebuie să mergem, este suficient să ne uităm la numărul de zerouri care apar în intervalul corespunzător vârfului stâng. Dacă acest număr precomputat este mai mare sau egal cu k, este necesar să coborâm la copilul stâng și altfel să coborâm la copilul drept. Observați, dacă am ales copilul potrivit, trebuie să scădem numărul de zerouri din copilul stâng din k.

În implementare putem gestiona cazul special, un a[] care conține mai puțin de k zerouri, prin returnarea -1.
int find_kth(int v, int tl, int tr, int k) {
    if (k > t[v])
        return -1;
    if (tl == tr)
        return tl;
    int tm = (tl + tr) / 2;
    if (t[v*2] >= k)
        return find_kth(v*2, tl, tm, k);
    else
        return find_kth(v*2+1, tm+1, tr, k - t[v*2]);
}
Căutarea unui prefix vectorul cu o sumă dată
Sarcina este următoarea: pentru o valoare dată x trebuie să găsim rapid cel mai mic indice i astfel încât suma primelor i elemente ale tabloului a [] să fie mai mare sau egală cu x (presupunând că tabloul a [] conține doar valori non-negative).

Această sarcină poate fi rezolvată folosind căutarea binară, calculând suma prefixelor cu Arborele Intervalului. Cu toate acestea, acest lucru va duce la o soluție O (log2n).

În schimb, putem folosi aceeași idee ca în secțiunea anterioară și putem găsi poziția coborând în copac: deplasându-ne de fiecare dată spre stânga sau spre dreapta, în funcție de suma copilului stâng. Găsind astfel răspunsul în timpul O (logn).

Căutarea primului element mai mare decât o anumită sumă
Sarcina este după cum urmează: pentru o valoare dată x și un interval a [l ... r] găsiți cel mai mic i din intervalul a [l ... r], astfel încât a [i] este mai mare decât x.

Această sarcină poate fi rezolvată folosind căutarea binară peste interogările de prefix maxim cu Arborele Intervalului. Cu toate acestea, acest lucru va duce la o soluție O (log2n).

În schimb, putem folosi aceeași idee ca în secțiunile anterioare și putem găsi poziția coborând în copac: deplasându-ne de fiecare dată spre stânga sau spre dreapta, în funcție de valoarea maximă a copilului stâng. Găsind astfel răspunsul în timpul O (logn).
int get_first(int v, int lv, int rv, int l, int r, int x) {
    if(lv > r || rv < l) return -1;
    if(l <= lv && rv <= r) {
        if(t[v] <= x) return -1;
        while(lv != rv) {
            int mid = lv + (rv-lv)/2;
            if(t[2*v] > x) {
                v = 2*v;
                rv = mid;
            }else {
                v = 2*v+1;
                lv = mid+1;
            }
        }
        return lv;
    }

    int mid = lv + (rv-lv)/2;
    int rs = get_first(2*v, lv, mid, l, r, x);
    if(rs != -1) return rs;
    return get_first(2*v+1, mid+1, rv, l ,r, x);
}

Găsirea subintervalelor cu suma maximă
Aici din nou primim un interval a [l ... r] pentru fiecare interogare, de data aceasta trebuie să găsim un subinterval a [l ′ ... r ′] astfel încât l≤l ′ și r′≤r și suma elementelor acest interval este maxim. Ca și înainte, dorim să putem modifica elemente individuale ale vectorului. Elementele vectorului pot fi negative și subintervalul optim poate fi gol (de exemplu, dacă toate elementele sunt negative).

Această problemă este o utilizare non-banală a unui arbore de intervale. De data aceasta vom stoca patru valori pentru fiecare vârf: suma intervalului, suma prefixului maxim, suma sufixului maxim și suma subintervalului maxim din acesta. Cu alte cuvinte, pentru fiecare interval al Arborelui Intervalului, răspunsul este deja precomputat, precum și răspunsurile pentru intervalele care ating limitele stânga și dreapta ale intervalului.

Cum se construiește un arbore cu astfel de date? Din nou îl calculăm într-un mod recursiv: calculăm mai întâi toate cele patru valori pentru copilul stâng și cel drept, apoi le combinăm pentru a arhiva cele patru valori pentru vârful curent. Rețineți că răspunsul pentru vârful curent este fie:

	răspunsul copilului stâng, ceea ce înseamnă că subintervalul optim este plasat în întregime în intervalul copilului stâng
	răspunsul copilului potrivit, ceea ce înseamnă că subintervalul optim este plasat în întregime în intervalul copilului potrivit
	suma sufixului maxim al copilului din stânga și suma prefixului maxim al copilului din dreapta, ceea ce înseamnă că subintervalul optim se intersectează cu ambii copii.
Prin urmare, răspunsul la vârful curent este maximul acestor trei valori. Calculul sumei maxime de prefix / sufix este și mai ușor. Iată implementarea funcției de combinare, care primește doar date de la copilul din stânga și din dreapta și returnează datele vârfului curent.

struct data {
    int sum, pref, suff, ans;
};

data combine(data l, data r) {
    data res;
    res.sum = l.sum + r.sum;
    res.pref = max(l.pref, l.sum + r.pref);
    res.suff = max(r.suff, r.sum + l.suff);
    res.ans = max(max(l.ans, r.ans), l.suff + r.pref);
    return res;
}

Folosind funcția de combinare este ușor să construiți Arborele intervalului. Îl putem implementa exact în același mod ca și în implementările anterioare. Pentru a inițializa vârfurile frunzei, creăm în plus funcția auxiliară make_data, care va returna un obiect de date care deține informațiile unei singure valori.
data make_data(int val) {
    data res;
    res.sum = val;
    res.pref = res.suff = res.ans = max(0, val);
    return res;
}

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = make_data(a[tl]);
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = make_data(new_val);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}
Rămâne doar cum să calculăm răspunsul la o interogare. Pentru a răspunde la aceasta, coborâm în copac ca înainte, împărțind interogarea în mai multe subintervale care coincid cu intervalele din Arborele intervalului și combinăm răspunsurile din ele într-un singur răspuns pentru interogare. Apoi ar trebui să fie clar că lucrarea este exact aceeași ca în arborele de intervale simplu, dar în loc să însumăm / minimizăm / maximizăm valorile, folosim funcția de combinare.
data query(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return make_data(0);
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return combine(query(v*2, tl, tm, l, min(r, tm)),
                   query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
Salvarea întregului subarrays în fiecare vârf
Aceasta este o subsecțiune separată care se deosebește de celelalte, deoarece la fiecare vârf al Arborelui Intervalului nu stocăm informații despre intervalul corespunzător sub formă comprimată (sumă, minim, maxim, ...), ci stocăm toate elementele intervalul. Astfel, rădăcina Arborelui intervalului va stoca toate elementele vectorului, vârful copil stâng va stoca prima jumătate a vectorului, vârful drept a doua jumătate și așa mai departe.

În cea mai simplă aplicare a acestei tehnici stocăm elementele în ordine sortată. În versiunile mai complexe elementele nu sunt stocate în liste, ci structuri de date mai avansate (seturi, hărți, ...). Dar toate aceste metode au factorul comun, că fiecare vârf necesită memorie liniară (adică proporțională cu lungimea intervalului corespunzător).

Prima întrebare naturală, atunci când se iau în considerare acești arbori de interval, este despre consumul de memorie. Intuitiv, acest lucru ar putea arăta ca o memorie O (n2), dar se dovedește că arborele complet va avea nevoie doar de memorie O (nlogn). De ce este așa? Pur și simplu, deoarece fiecare element al vectorului se încadrează în intervale O (logn) (amintiți-vă că înălțimea arborelui este O (logn)).

Deci, în ciuda aparentei extravaganțe a unui astfel de arbore de intervale, acesta consumă doar puțin mai multă memorie decât arborele de interval obișnuit.

Mai multe aplicații tipice ale acestei structuri de date sunt descrise mai jos. Merită remarcat similaritatea acestor arbori de intervale cu structuri de date 2D (de fapt aceasta este o structură de date 2D, dar cu capacități destul de limitate).

Găsiți cel mai mic număr mai mare sau egal cu un număr specificat. Fără interogări de modificare.
Vrem să răspundem la întrebări de următoarea formă: pentru trei numere date (l, r, x) trebuie să găsim numărul minim din intervalul a [l ... r] care este mai mare sau egal cu x.

Construim un arbore de intervale. În fiecare vârf stocăm o listă sortată a tuturor numerelor care apar în intervalul corespunzător, așa cum este descris mai sus. Cum să construiești un astfel de arbore de interval cât mai eficient posibil? Ca întotdeauna, abordăm această problemă recursiv: să fie deja construite listele copiilor din stânga și din dreapta și vrem să construim lista pentru vârful curent. Din această perspectivă, operațiunea este acum banală și poate fi realizată în timp liniar: trebuie doar să combinăm cele două liste sortate într-una singură, care se poate face prin iterația peste ele folosind doi indicatori. C ++ STL are deja o implementare a acestui algoritm.

Deoarece această structură a Arborelui Intervalului și asemănările cu algoritmul de sortare a fuzionării, structura datelor este, de asemenea, numită adesea „Arborele de sortare Merge”.
vector<int> t[4*MAXN];

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = vector<int>(1, a[tl]);
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        merge(t[v*2].begin(), t[v*2].end(), t[v*2+1].begin(), t[v*2+1].end(),
              back_inserter(t[v]));
    }
}
Știm deja că Arborele Intervalului construit în acest mod va necesita memorie O (nlogn). Și datorită acestei implementări, construcția sa necesită și O (nlogn) timp, după toate fiecare listă este construită în timp liniar în funcție de dimensiunea sa.

Acum ia în considerare răspunsul la interogare. Vom coborî în copac, ca în Arborele de Interval obișnuit, rupând intervalul nostru [l ... r] în mai multe subintervale (în cel mult O (logn) bucăți). Este clar că răspunsul întregului răspuns este minimul fiecărei subinterogări. Deci, acum trebuie doar să înțelegem cum să răspundem la o interogare pe un astfel de subinterval care corespunde cu un anumit vârf al arborelui.

Ne aflăm la un anumit vârf al Arborelui Intervalului și dorim să calculăm răspunsul la interogare, adică să găsim numărul minim mai mare sau egal cu un număr dat x. Întrucât vârful conține lista elementelor în ordine sortată, putem pur și simplu efectua o căutare binară pe această listă și returnăm primul număr, mai mare sau egal cu x.

Astfel, răspunsul la interogarea într-un interval al arborelui durează O (logn) timp, iar întreaga interogare este procesată în O (log2n).
int query(int v, int tl, int tr, int l, int r, int x) {
    if (l > r)
        return INF;
    if (l == tl && r == tr) {
        vector<int>::iterator pos = lower_bound(t[v].begin(), t[v].end(), x);
        if (pos != t[v].end())
            return *pos;
        return INF;
    }
    int tm = (tl + tr) / 2;
    return min(query(v*2, tl, tm, l, min(r, tm), x),
               query(v*2+1, tm+1, tr, max(l, tm+1), r, x));
}
INF constantă este egal cu un număr mare care este mai mare decât toate numerele din vectorul. Utilizarea acestuia înseamnă că nu există un număr mai mare sau egal cu x în interval. Are semnificația „nu există răspuns în intervalul dat”.

Găsiți cel mai mic număr mai mare sau egal cu un număr specificat. Cu interogări de modificare.
Această sarcină este similară cu cea anterioară. Ultima abordare are un dezavantaj, nu a fost posibil să se modifice vectorula între răspunsuri la interogări. Acum vrem să facem exact acest lucru: o interogare de modificare va face misiunea a [i] = y.

Soluția este similară cu soluția problemei anterioare, dar în loc de liste la fiecare vârf al arborelui intervalului, vom stoca o listă echilibrată care vă permite să căutați rapid numere, să ștergeți numere și să inserați numere noi. Deoarece vectorula poate conține un număr repetat, alegerea optimă este structura de date multiset.

Construcția unui astfel de arbore de intervale se face cam în același mod ca și în problema anterioară, doar că acum trebuie să combinăm multiseturi și nu liste sortate. Acest lucru duce la un timp de construcție de O (nlog2n) (în general, fuzionarea a doi arbori roșu-negri se poate face în timp liniar, dar STL C ++ nu garantează această complexitate de timp).

Funcția de interogare este, de asemenea, aproape echivalentă, doar că acum funcția lower_bound a funcției multiset ar trebui apelată în schimb (std :: lower_bound funcționează numai în timp O (logn) dacă este utilizat cu iteratoare cu acces aleatoriu).

În cele din urmă, cererea de modificare. Pentru a procesa, trebuie să coborâm în copac și să modificăm toate multiseturile din intervalele corespunzătoare care conțin elementul efectat. Ștergem pur și simplu vechea valoare a acestui element (dar o singură apariție) și inserăm noua valoare.
void update(int v, int tl, int tr, int pos, int new_val) {
    t[v].erase(t[v].find(a[pos]));
    t[v].insert(new_val);
    if (tl != tr) {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
    } else {
        a[pos] = new_val;
    }
}
Procesarea acestei interogări de modificare necesită, de asemenea, O (log2n) timp.



Găsiți cel mai mic număr mai mare sau egal cu un număr specificat. Accelerare cu „cascadă fracționată”.
Avem aceeași afirmație de problemă, vrem să găsim numărul minim mai mare sau egal cu x într-un interval, dar de data aceasta în timp O (logn). Vom îmbunătăți complexitatea timpului folosind tehnica „cascadă fracționată”.

Fracționarea în cascadă este o tehnică simplă care vă permite să îmbunătățiți timpul de rulare al mai multor căutări binare, care sunt efectuate în același timp. Abordarea noastră anterioară a interogării de căutare a fost aceea că împărțim sarcina în mai multe subtaskuri, fiecare dintre acestea fiind rezolvată cu o căutare binară. Fracționarea în cascadă vă permite să înlocuiți toate aceste căutări binare cu una singură.

Cel mai simplu și mai evident exemplu de cascadă fracționată este următoarea problemă: există k liste sortate de numere și trebuie să găsim în fiecare listă primul număr mai mare sau egal cu numărul dat.

În loc să efectuăm o căutare binară pentru fiecare listă, am putea îmbina toate listele într-o listă mare sortată. În plus, pentru fiecare element y stocăm o listă a rezultatelor căutării lui y în fiecare din k listele. Prin urmare, dacă dorim să găsim cel mai mic număr mai mare sau egal cu x, trebuie doar să efectuăm o singură căutare binară și din lista de indici putem determina cel mai mic număr din fiecare listă. Această abordare necesită totuși O (n⋅k) (n este lungimea listelor combinate), care poate fi destul de ineficientă.

Cascadarea fracțională reduce această complexitate a memoriei la O (n) memorie, creând din k listele de intrare k noi liste, în care fiecare listă conține lista corespunzătoare și, de asemenea, fiecare al doilea element din următoarea nouă listă. Folosind această structură este necesar doar să stocați doi indici, indexul elementului în lista originală și indexul elementului din următoarea listă nouă. Deci, această abordare utilizează doar memoria O (n) și totuși poate răspunde la întrebări folosind o singură căutare binară.

Dar pentru aplicația noastră nu avem nevoie de toată puterea cascadării fracționate. În Arborele nostru de intervale, un vârf va conține lista sortată a tuturor elementelor care apar în subarborii din stânga sau din dreapta (cum ar fi în Arborele de sortare Merge). În plus față de această listă sortată, stocăm două poziții pentru fiecare element. Pentru un element y stocăm cel mai mic index i, astfel încât elementul i din lista sortată a copilului din stânga este mai mare sau egal cu y. Și stocăm cel mai mic index j, astfel încât elementul j în lista sortată a copilului potrivit este mai mare sau egal cu y. Aceste valori pot fi calculate în paralel cu pasul de fuzionare atunci când construim arborele.

Cum accelerează acest lucru interogările?

Amintiți-vă, în soluția normală am făcut o căutare binară în vreun nod. Dar, cu această modificare, putem evita toate, cu excepția uneia.

Pentru a răspunde la o interogare, pur și simplu la o căutare binară în nodul rădăcină. Aceasta dă ca cel mai mic element y≥x din vectorula completă, dar ne oferă și două poziții. Indicele celui mai mic element mai mare sau egal x în subarborele din stânga și indicele celui mai mic element y din subarborele din dreapta. Observați că ≥y este același cu ≥x, deoarece vectorula noastră nu conține elemente între x și y. În soluția normală Merge Sort Tree, am calcula acești indici prin căutare binară, dar cu ajutorul valorilor precomputate le putem căuta în O (1). Și putem repeta asta până când am vizitat toate nodurile care acoperă intervalul de interogare.

Pentru a rezuma, ca de obicei, atingem nodurile O (logn) în timpul unei interogări. În nodul rădăcină facem o căutare binară, iar în toate celelalte noduri facem doar o muncă constantă. Aceasta înseamnă că complexitatea pentru a răspunde la o interogare este O (logn).

Dar observați că aceasta folosește de trei ori mai multă memorie decât un arbore de sortare Merge normal, care folosește deja multă memorie (O (nlogn)).

Este simplu să aplicați această tehnică unei probleme, care nu necesită nicio interogare de modificare. Cele două poziții sunt doar numere întregi și pot fi ușor calculate prin numărare la fuzionarea celor două secvențe sortate.

Este încă posibil să permiți și interogări de modificare, dar acest lucru complică întregul cod. În loc de numere întregi, trebuie să stocați vectorula sortată ca multiset și, în loc de indici, trebuie să stocați iteratorii. Și trebuie să lucrați foarte atent, astfel încât să creșteți sau să decrementați iteratorii corecți în timpul unei interogări de modificare.

Alte variante posibile
Această tehnică implică o nouă clasă de aplicații posibile. În loc să stocheze un vector sau un multiset în fiecare vârf, pot fi utilizate alte structuri de date: alți arbori de interval (oarecum discutați în Generalizare la dimensiuni superioare), arbori Fenwick, arbori cartezieni etc.

Actualizări ale intervalului (Lazy Propagation)

Toate problemele din secțiunile de mai sus au discutat interogările de modificare care au efectuat doar câte un singur element al vectorului. Cu toate acestea, Arborele Intervalului permite aplicarea interogărilor de modificare unui întreg interval de elemente adiacente și efectuarea interogării în același timp O (logn).

Adăugare pe intervale
Începem prin a lua în considerare problemele de cea mai simplă formă: interogarea de modificare ar trebui să adauge un număr x tuturor numerelor din intervalul a [l ... r]. A doua interogare, la care ar trebui să răspundem, a cerut pur și simplu valoarea unui a[i].

Pentru a eficientiza interogarea de adăugare, stocăm la fiecare vârf din Arborele intervalului câte ar trebui să adăugăm la toate numerele din intervalul corespunzător. De exemplu, dacă interogarea „adaugă 3 la întreagul vectorul apare un [0… n − 1]”, atunci plasăm numărul 3 în rădăcina arborelui. În general, trebuie să plasăm acest număr de mai multe la mai multe intervale, care formează o partiție a intervalului de interogare. Astfel, nu trebuie să schimbăm toate valorile O (n), ci doar O (logn) multe.

Dacă acum apare o interogare care solicită valoarea curentă a unei anumite intrări vectorul, este suficient să coborâți în copac și să adăugați toate valorile găsite pe parcurs.

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, int add) {
    if (l > r)
        return;
    if (l == tl && r == tr) {
        t[v] += add;
    } else {
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), add);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
    }
}

int get(int v, int tl, int tr, int pos) {
    if (tl == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return t[v] + get(v*2, tl, tm, pos);
    else
        return t[v] + get(v*2+1, tm+1, tr, pos);
}

Atribuire pe intervale
Să presupunem acum că interogarea de modificare solicită atribuirea fiecărui element al unui anumit interval a [l ... r] la o anumită valoare p. Ca a doua interogare, vom lua din nou în considerare citirea valorii vectorul a [i].

Pentru a efectua această interogare de modificare pe un interval întreg, trebuie să stocați la fiecare vârf al Arborelui intervalului dacă intervalul corespunzător este acoperit în totalitate cu aceeași valoare sau nu. Acest lucru ne permite să facem o actualizare „leneșă”: în loc să schimbăm toate intervalele din arborele care acoperă intervalul de interogare, schimbăm doar unele și lăsăm altele neschimbate. Un vârf marcat va însemna că fiecare element al intervalului corespunzător este atribuit acelei valori și, de fapt, subarborele complet trebuie să conțină doar această valoare. Într-un anumit sens, suntem leneși și întârziem să scriem noua valoare la toate aceste vârfuri. Putem face această sarcină obositoare mai târziu, dacă este necesar.

Deci, după executarea interogării de modificare, unele părți ale arborelui devin irelevante - unele modificări rămân neîndeplinite.

De exemplu, dacă o interogare de modificare „atribuie un număr întregului tablou se execută un [0… n − 1]”, în Arborele Intervalului se face o singură modificare - numărul este plasat în rădăcina arborelui și acest vârf se marchează. Intervalele rămase rămân neschimbate, deși numărul ar trebui să fie plasat în întregul copac.

Să presupunem acum că a doua interogare de modificare spune că prima jumătate a vectorul a [0 ... n / 2] ar trebui alocată cu un alt număr. Pentru a procesa această interogare, trebuie să atribuim fiecărui element din întregul copil stânga al vârfului rădăcină cu acel număr. Dar, înainte de a face acest lucru, trebuie mai întâi să sortăm vârful rădăcinii mai întâi. Subtilitatea de aici este că jumătatea dreaptă a vectorul ar trebui să fie atribuită în continuare valorii primei interogări și, în acest moment, nu există informații pentru jumătatea dreaptă stocată.

Modul de a rezolva acest lucru este de a împinge informațiile rădăcinii către copiii săi, adică dacă rădăcina arborelui a fost atribuită cu orice număr, atunci atribuim vârfurile copil stânga și dreapta cu acest număr și eliminăm marca rădăcinii . După aceea, putem atribui copilului stâng cu noua valoare, fără a pierde informațiile necesare.

Rezumând obținem: pentru orice întrebări (o interogare de modificare sau citire) în timpul coborârii de-a lungul copacului, ar trebui să împingem întotdeauna informații de pe vârful curent în ambii copii ai acestuia. Putem înțelege acest lucru în așa fel încât, atunci când coborâm arborele, aplicăm modificări întârziate, dar exact cât este necesar (astfel încât să nu degradăm complexitatea lui O (logn).

Pentru implementare, trebuie să realizăm o funcție push, care va primi vârful curent și va împinge informațiile pentru vârful său atât pentru copiii săi. Vom numi această funcție la începutul funcțiilor de interogare (dar nu o vom apela din frunze, deoarece nu este nevoie să împingem informații de la ele mai departe).
void push(int v) {
    if (marked[v]) {
        t[v*2] = t[v*2+1] = t[v];
        marked[v*2] = marked[v*2+1] = true;
        marked[v] = false;
    }
}

void update(int v, int tl, int tr, int l, int r, int new_val) {
    if (l > r)
        return;
    if (l == tl && tr == r) {
        t[v] = new_val;
        marked[v] = true;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), new_val);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, new_val);
    }
}

int get(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        return t[v];
    }
    push(v);
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return get(v*2, tl, tm, pos);
    else
        return get(v*2+1, tm+1, tr, pos);
}

Comprimarea arborelui intervalului 2D

Fie problema următoarea: există n puncte pe plan date de coordonatele lor (xi, yi) și interogările de formă „numără numărul de puncte aflate în dreptunghi ((x1, y1), (x2, y2) ) ". Este clar că, în cazul unei astfel de probleme, devine irosibil de irosit să construim un arbore de intervale bidimensional cu elemente O (n2). Cea mai mare parte din această memorie va fi irosită, deoarece fiecare punct unic poate intra în intervale O (logn) ale arborelui de-a lungul primei coordonate și, prin urmare, dimensiunea totală „utilă” a tuturor intervalelor de arbore de pe a doua coordonată este O (nlogn) .

Deci procedăm după cum urmează: la fiecare vârf al Arborelui Intervalului în raport cu prima coordonată stocăm un Arborele Intervalului construit numai de acele a doua coordonate care apar în intervalul curent al primelor coordonate. Cu alte cuvinte, atunci când construim un arbore de intervale în interiorul unui vârf cu index vx și limitele tlx și trx, luăm în considerare doar acele puncte care se încadrează în acest interval x∈ [tlx, trx] și construim un arbore de intervale doar folosindu-le.

Astfel vom realiza că fiecare arbore de intervale de pe a doua coordonată va ocupa exact câtă memorie ar trebui. Ca urmare, cantitatea totală de memorie va scădea la O (nlogn). Încă putem răspunde la întrebări în timp O (log2n), trebuie doar să facem o căutare binară pe a doua coordonată, dar acest lucru nu va agrava complexitatea.

Dar interogările de modificare vor fi imposibile cu această structură: de fapt, dacă apare un punct nou, trebuie să adăugăm un element nou în mijlocul unui arbore de intervale de-a lungul celei de-a doua coordonate, care nu poate fi realizat în mod eficient.

În concluzie, observăm că Arborele Intervalului bidimensional contractat în modul descris devine practic echivalent cu modificarea Arborelui Intervalului unidimensional (vezi Salvarea întregului subarray în fiecare vârf). În special Arborele Intervalului bidimensional este doar un caz special de stocare a unui subarray în fiecare vârf al arborelui. Rezultă că, dacă ați dat să abandonați un arbore de intervale bidimensional din cauza imposibilității de a executa o interogare, este logic să încercați să înlocuiți arborele de interval imbricat cu o structură de date mai puternică, de exemplu un arbore cartezian.

Păstrarea istoriei valorilor sale (Arborele intervalului persistent)
O structură de date persistentă este o structură de date care își amintește starea anterioară pentru fiecare modificare. Acest lucru permite accesarea oricărei versiuni a acestei structuri de date care ne interesează și executarea unei interogări pe aceasta.

Interval Tree este o structură de date care poate fi transformată într-o structură de date persistentă în mod eficient (atât în timp cât și în consumul de memorie). Vrem să evităm copierea arborelui complet înainte de fiecare modificare și nu vrem să pierdem comportamentul de timp O (logn) pentru a răspunde la interogări de gamă.

De fapt, orice cerere de modificare din Arborele Intervalului duce la o modificare a datelor numai a vârfurilor O (logn) de-a lungul căii, începând de la rădăcină. Deci, dacă stocăm Arborele Intervalului folosind pointeri (adică un vârf stochează pointeri la vârfurile stânga și dreapta copil), atunci când efectuăm interogarea de modificare, trebuie pur și simplu să creăm vârfuri noi în loc să schimbăm vârfurile disponibile. Vârfurile care nu sunt afectate de interogarea de modificare pot fi utilizate în continuare prin îndreptarea indicatorilor către vârfurile vechi. Astfel, pentru o interogare de modificare O (logn) vor fi creați noi vârfuri, inclusiv un nou vârf rădăcină al Arborelui intervalului, iar întreaga versiune anterioară a arborelui înrădăcinată la vârful rădăcinii vechi va rămâne neschimbată.

Să dăm un exemplu de implementare pentru cel mai simplu arbore de intervale: atunci când există doar o interogare care solicită sume și interogări de modificare pentru elemente individuale.
struct Vertex {
    Vertex *l, *r;
    int sum;

    Vertex(int val) : l(nullptr), r(nullptr), sum(val) {}
    Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0) {
        if (l) sum += l->sum;
        if (r) sum += r->sum;
    }
};

Vertex* build(int a[], int tl, int tr) {
    if (tl == tr)
        return new Vertex(a[tl]);
    int tm = (tl + tr) / 2;
    return new Vertex(build(a, tl, tm), build(a, tm+1, tr));
}

int get_sum(Vertex* v, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l == tl && tr == r)
        return v->sum;
    int tm = (tl + tr) / 2;
    return get_sum(v->l, tl, tm, l, min(r, tm))
         + get_sum(v->r, tm+1, tr, max(l, tm+1), r);
}

Vertex* update(Vertex* v, int tl, int tr, int pos, int new_val) {
    if (tl == tr)
        return new Vertex(new_val);
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return new Vertex(update(v->l, tl, tm, pos, new_val), v->r);
    else
        return new Vertex(v->l, update(v->r, tm+1, tr, pos, new_val));
}
Pentru fiecare modificare a Arborelui Intervalului vom primi un nou vârf rădăcină. Pentru a trece rapid între două versiuni diferite ale Arborelui intervalului, trebuie să stocăm aceste rădăcini într-o vector. Pentru a utiliza o versiune specifică a Arborelui intervalului, apelăm pur și simplu interogarea folosind vârful rădăcină corespunzător.

Cu abordarea descrisă mai sus, aproape orice arbore de intervale poate fi transformat într-o structură de date persistentă.

Găsirea celui de-al treilea cel mai mic număr dintr-un interval
De data aceasta trebuie să răspundem la întrebări de forma „Care este cel de-al patrulea cel mai mic element din gama a [l ... r]. La această interogare se poate răspunde folosind o căutare binară și un arbore Merge Sort, dar complexitatea timpului o singură interogare ar fi O (log3n). Vom realiza aceeași sarcină folosind un arbore de intervale persistent în O (logn).

Mai întâi vom discuta o soluție pentru o problemă mai simplă: vom lua în considerare doar matrici în care elementele sunt legate de 0≤a [i] <n. Și vrem să găsim cel mai mic element k-th într-un prefix al vectorul a. Va fi foarte ușor să extindeți ideile dezvoltate mai târziu pentru interogări nelimitate și interogări de domeniu nelimitat. Rețineți că vom folosi 1 indexare bazată pe un.

Vom folosi un arbore de intervale care numără toate numerele care apar, adică în arborele de intervale vom stoca histograma vectorul. Deci, vârfurile frunzelor vor stoca cât de des vor apărea valorile 0, 1, ..., n − 1 în vector, iar celelalte vârfuri stochează câte numere dintr-o anumită gamă sunt în vector. Cu alte cuvinte, creăm un arbore de intervale obișnuit cu interogări de sumă peste histograma vectorul. Dar, în loc să creăm toți n arbori de interval pentru fiecare posibil prefix, vom crea unul persistent, care va conține aceleași informații. Vom începe cu un arbore de intervale gol (toate numărările vor fi 0) indicat de root0 și vom adăuga elementele a [1], a [2],…, a [n] unul după altul. Pentru fiecare modificare vom primi un nou vârf rădăcină, să numim rooti rădăcina Arborelui intervalului după inserarea primelor elemente i ale vectorul a. Arborele intervalului înrădăcinat la rooti va conține histograma prefixului a [1 ... i]. Folosind acest arbore de intervale putem găsi în timpul O (logn) poziția elementului k-th folosind aceeași tehnică discutată în Numărarea numărului de zerouri, căutând k-th zero.

Acum, la versiunea fără restricții a problemei.

Mai întâi pentru restricția privind interogările: În loc să efectuăm aceste interogări numai peste un prefix al lui a, vrem să folosim orice intervale arbitrare a [l ... r]. Aici avem nevoie de un arbore de intervale care să reprezinte histograma elementelor din intervalul a [l ... r]. Este ușor de văzut că un astfel de arbore de intervale este doar diferența dintre arborele de intervale înrădăcinat la rootr și arborele de interval înrădăcinat la rootl − 1, adică fiecare vârf din arborele de intervale [l ... r] poate fi calculat cu vârful lui arborele rootr minus vârful arborelui rootl − 1.

În implementarea funcției find_kth acest lucru poate fi gestionat prin trecerea a două pointeri de vârf și calcularea numărului / sumei intervalului curent ca diferență a celor două număruri / sume ale vârfurilor.

Iată funcțiile modificate de construire, actualizare și find_kth
Vertex* build(int tl, int tr) {
    if (tl == tr)
        return new Vertex(0);
    int tm = (tl + tr) / 2;
    return new Vertex(build(tl, tm), build(tm+1, tr));
}

Vertex* update(Vertex* v, int tl, int tr, int pos) {
    if (tl == tr)
        return new Vertex(v->sum+1);
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return new Vertex(update(v->l, tl, tm, pos), v->r);
    else
        return new Vertex(v->l, update(v->r, tm+1, tr, pos));
}

int find_kth(Vertex* vl, Vertex *vr, int tl, int tr, int k) {
    if (tl == tr)
        return tl;
    int tm = (tl + tr) / 2, left_count = vr->l->sum - vl->l->sum;
    if (left_count >= k)
        return find_kth(vl->l, vr->l, tl, tm, k);
    return find_kth(vl->r, vr->r, tm+1, tr, k-left_count);
}
După cum s-a scris deja mai sus, trebuie să stocăm rădăcina arborelui intervalului inițial și, de asemenea, toate rădăcinile după fiecare actualizare. Iată codul pentru construirea unui arbore de intervale persistent peste un vector a cu elemente în intervalul [0, MAX_VALUE].
int tl = 0, tr = MAX_VALUE + 1;
std::vector<Vertex*> roots;
roots.push_back(build(tl, tr));
for (int i = 0; i < a.size(); i++) {
    roots.push_back(update(roots.back(), tl, tr, a[i]));
}

// find the 5th smallest number from the subarray [a[2], a[3], ..., a[19]]
int result = find_kth(roots[2], roots[20], tl, tr, 5);

Acum, la restricțiile asupra elementelor vectorul: Putem transforma de fapt orice vector într-o astfel de vector prin compresie index. Cel mai mic element din vector va primi valoarea 0, al doilea cel mai mic valoarea 1 și așa mai departe. Este ușor să generați tabele de căutare (de exemplu, folosind harta), care convertesc o valoare la indexul său și invers în timp O (logn).

Arborele intervalului implicit
Anterior, am luat în considerare cazurile în care avem capacitatea de a construi arborele intervalului original. Dar ce trebuie făcut dacă dimensiunea originală este umplută cu un element implicit, dar dimensiunea sa nu vă permite să vă construiți complet în avans?

Putem rezolva această problemă fără a crea în mod explicit un arbore de intervale. Inițial, vom crea doar rădăcina și vom crea celelalte vârfuri doar atunci când vom avea nevoie de ele. În acest caz, vom folosi implementarea pe pointeri (înainte de a merge la copiii vertex, verificați dacă sunt creați și, dacă nu, creați-i). Fiecare interogare are încă doar complexitatea O (logn), care este suficient de mică pentru majoritatea cazurilor de utilizare (de exemplu log2109≈30).

În această implementare avem două interogări, adăugând o valoare la o poziție (inițial toate valorile sunt 0) și calculând suma tuturor valorilor dintr-un interval. Vertexul (0, n) va fi vârful rădăcinii arborelui implicit.
struct Vertex {
    int left, right;
    int sum = 0;
    Vertex *left_child = nullptr, *right_child = nullptr;

    Vertex(int lb, int rb) {
        left = lb;
        right = rb;
    }

    void extend() {
        if (!left_child && left + 1 < right) {
            int t = (left + right) / 2;
            left_child = new Vertex(left, t);
            right_child = new Vertex(t, right);
        }
    }

    void add(int k, int x) {
        extend();
        sum += x;
        if (left_child) {
            if (k < left_child->right)
                left_child->add(k, x);
            else
                right_child->add(k, x);
        }
    }

    int get_sum(int lq, int rq) {
        if (lq <= left && right <= rq)
            return sum;
        if (max(left, lq) >= min(right, rq))
            return 0;
        extend();
        return left_child->get_sum(lq, rq) + right_child->get_sum(lq, rq);
    }
};