Poti pleca de la reprezentarea unui arbore de intervale. Un nod dintr-un arbore de intervale caracterizeaza un interval, (st, dr) sa zicem. Acum sa presupunem ca iti mentii urmatoarele informatii pt fiecare astfel de nod:
1) o lista cu valorile din intervalul (st, dr) in ordine crescatoare. Aceasta lista se poate obtine prin interclasarea listelor fiilor acelui nod. Avand in vedere ca fiecare valoare apare in log N noduri, complexitatea dpdv al memoriei cat si al timpului este N log N la pasul asta.
2) conceptual vei mentine o alta lista de lungime nr de noduri, unde pe pozitia i, ai 1 daca valoarea i(in ordinea sortata de mai sus) e online, 0 altfel. Avand in vedere tipurile de operatii pe care vrei sa le executi, defapt iti vei mentine un aib de lungime tot nr de noduri care este construit pe baza listei de care spuneam. Pt stocarea acestor aib-uri este necesara de asemenea, tot N log N memorie.
Cu aceste informatii, poti sa aplici acum operatiile date in felul urmator:
Operatie de tip 1: Vei trece prin cele log N noduri din arborele de intervale care contin nodul p din enunt si le vei actualiza aib-ul asociat. Deci log ^ 2 N / operatie de acest tip
Operatie de tip 2: Vei descompune intervalul (p, q) in log N noduri. Acum cauti binar rezultatul printre cele N valori posibile(presupunand ca mai ai o lista cu valorile initiale sortate in ordine crescatoare). Pt o anumita valoare, verificarea se poate face folosind structura de aib, in log (lungime nod) pt fiecare nod. Complexitatea teoretica e in cazul asta log ^ 3 N, dar se comporta destul de bine.
Bafta!
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena