Arbori indexaţi binar

Acest articol a fost adăugat de Marius Stroe •Marius Intră aici dacă doreşti să scrii articole sau află cum te poţi implica în celelalte proiecte infoarena!

(Categoria Structuri de date, Autor Mihai Scorţaru)

• Conţinut:
• Introducere

Problema determinării sumei elementelor unei subsecvenţe a unui şir ale cărui valori se modifică în timp real apare destul de des în diferite aplicaţii. Ea a apărut, sub diverse forme şi la anumite concursuri de programare. În cadrul acestui articol vom prezenta o structură de date care poate fi folosită pentru rezolvarea eficientă a acestei probleme.

Introducere

Prin subsecvenţă înţelegem un subşir ale cărui elemente se află pe poziţii consecutive în şirul iniţial. De exemplu, (2, 3, 4) este o subsecvenţă a şirului (1, 2, 3, 4, 5) formată din al doilea, al treilea şi al patrulea element al şirului, în timp ce (1, 2, 4) nu este o subsecvenţă deoarece nu este formată din elemente aflate pe poziţii consecutive.

În cadrul acestui articol vom identifica o subsecvenţă prin extremităţile sale (poziţia cea mai din stânga şi poziţia cea mai din dreapta din şir). O subsecvenţă care începe în poziţia a şi se termină în poziţia b va fi notată cu <a, b>. Pentru şirul (1, 2, 3, 4, 5) subsecvenţa (2, 3, 4) va fi notată prin <2, 4> dacă numerotarea elementelor începe cu 1 sau prin <1, 3> dacă numerotarea începe de la 0.

Deseori, avem nevoie de informaţii referitoare la subsecvenţele unui şir cum ar fi suma elementelor, produsul lor, valoarea minimă, valoarea maximă etc. La prima vedere, rezolvarea acestei probleme pare destul de simplă (de exemplu, pentru sumă se parcurg elementele subsecvenţei şi se adună). Totuşi, acest algoritm este ineficient datorită faptului că necesită parcurgerea întregii subsecvenţe. Vom arăta că există algoritmi pentru care o astfel de parcurgere nu este necesară.

Totuşi, dacă am efectua o singură dată sau de un număr limitat de ori o astfel de parcurgere, algoritmul ar putea părea performant, viteza de execuţie fiind relativ mare. Problema se complică dacă elementele şirului se modifică în timp real.

Modificări în timp real

Să presupunem că există două tipuri de operaţii care pot fi efectuate asupra unui şir. Primul tip constă în modificarea valorii unui element, în timp ce al doilea reprezintă interogări (cereri de informaţii) referitoare la anumite subsecvenţe ale şirului. De obicei, cele două tipuri de operaţii sunt "amestecate" în sensul că nu vor fi doar modificări urmate din interogări, ci putem avea o modificare, urmată de două interogări, urmate de cinci modificări, urmate de alte două interogări etc.

Aşadar, putem spune că elementele şirului se modifică în timp real şi interogările se referă la starea curentă a şirului (cea din momentul cererii de informaţii).

Enunţul problemei

În cele ce urmează vom prezenta un enunţ al problemei, particularizat pentru cazul în care interogările se referă la suma elementelor subsecvenţelor.

Se consideră un şir de numere întregi care are toate elementele nule. O modificare a unui element constă în adunarea unei valori la valoarea curentă (pot fi realizate şi scăderi care au forma adunării unor valori negative). Pe parcursul modificărilor pot apărea interogări referitoare la suma elementelor unei subsecvenţe a şirului.

Problema poate fi enunţată în multe alte forme. Una dintre ele ar putea fi următoarea...

Un furnizor lucrează cu N distribuitori; în fiecare moment distribuitorii pot efectua plăţi sau pot cumpăra produse. De asemenea, în fiecare moment furnizorul poate cere informaţii referitoare la suma totală a datoriilor pe care le au magazinele cu numere de ordine cuprinse între două valori date.

(?) Evident, există multe alte enunţuri echivalente. De asemenea, pot apărea enunţuri în care operaţia de însumare ar putea fi înlocuită cu altele. De exemplu, furnizorul ar putea dori să cunoască datoria maximă a unui magazin care are numărul de ordine cuprins între două valori date.

Exemplu

Vom exemplifica acum evoluţia în timp real a unui şir format din cinci elemente, prezentând valorile şirului după fiecare modificare şi rezultatul fiecărei interogări.

Operaţia Iniţializare constã în setarea la 0 a valorilor tuturor elementelor. Operaţia Adună(i, x) constă în adunarea valorii x la valoarea curentă a celui de al i-lea element. Operaţia Sumă(a, b) furnizează suma elementelor subsecvenţei <a, b>.

Cazul unidimensional

Din modul în care a fost enunţată problema, rezultă că operaţiile sunt efectuate asupra unui tablou unidimensional; aşadar, acesta este cazul unidimensional al problemei. Vom prezenta în continuare trei algoritmi care pot fi folosiţi pentru rezolvarea problemei şi apoi le vom studia performanţele.

Algoritmul naiv

Cea mai intuitivă metodă de rezolvare constă în păstrarea unui vector cu valorile şirului, modificarea lor atunci când este necesar şi calcularea sumelor în momentul în care apar interogări.

Pentru a prezenta algoritmul vom considera că o modificare este codificată prin valoarea 1, iar o interogare prin valoarea 2. Ar fi necesară o a treia operaţie (codificată prin 3) car ar indica faptul că nu mai există modificări sau interogări, deci execuţia poate fi încheiată.

Versiunea în pseudocod este prezentată în continuare:

// iniţializări

scrie „Introduceţi numărul de elemente:”
citeşte N        // dimensiunea şirului
pentru i = 1, N execută
    a[i] = 0        // valorile iniţiale sunt nule
sfârşit pentru
scrie „Introduceţi codul operaţiei:”

citeşte cod
cât timp cod <> 3 execută
    dacă cod = 1 atunci    // modificare
        scrie „Introduceţi indicele elementului care va fi modificat:”
        citeşte ind
        scrie „Introduceţi valoarea care va fi adunată (valoare negativă pentru scăderi):”
        citeşte val
        a[ind] = a[ind] + val
    altfel    // interogare
        scrie „Introduceţi extremităţile subsecvenţei:”
        citeşte st, dr
        sumă = 0
        pentru i = st, dr execută
            sumă = sumă + a[i]
        sfârşit pentru
        scrie „Suma elementelor subsecvenţei este: ”, sumă
    sfârşit dacă
    scrie „Introduceţi codul operaţiei:”
    citeşte cod
sfârşit cât timp

Se observă că modificările se efectuează în timp constant deoarece implică doar accesarea unui element al vectorului şi modificarea valorii sale.

Datorită faptului că pentru calcularea sumei elementelor unei subsecvenţe este necesară parcurgerea tuturor elementelor subsecvenţei, această operaţie are ordinul de complexitate O(L), unde L este lungimea subsecvenţei.

Trebuie observat faptul că algoritmul este acelaşi dacă operaţia de însumare este înlocuită cu o alta (calcularea produsului, stabilirea minimului etc.).

Vector de sume

O altă idee este de a menţine un vector S cu semnificaţia S _i = suma elementelor din subsecventa <1, i>. Astfel, răspunsul la o întrebare (x, y) va fi S _y - S _x-1, ce se poate calcula în timp constant. Însă, când se modifică un element a _i trebuie modificate toate sumele S _i, S _i+1 ... S _n, deci timpul necesar pentru o modificare este liniar proporţional cu lungimea şirului.

Implementarea (scrisă in pseudocod) este aceasta:

// iniţializări

scrie „Introduceţi numărul de elemente:”
citeşte N        // dimensiunea şirului
pentru i = 1, N execută
    S[i] = 0        // valorile iniţiale sunt nule
sfârşit pentru
scrie „Introduceţi codul operaţiei:”

citeşte cod
cât timp cod <> 3 execută
    dacă cod = 1 atunci    // modificare
        scrie „Introduceţi indicele elementului care va fi modificat:”
        citeşte ind
        scrie „Introduceţi valoarea care va fi adunată (valoare negativă pentru scăderi):”
        citeşte val
        pentru i = ind, n execută
            S[i] = S[i] + val
        sfârşit pentru
    altfel    // interogare
        scrie „Introduceţi extremităţile subsecvenţei:”
        citeşte st, dr
        scrie „Suma elementelor subsecvenţei este: ”, S[dr] - S[st - 1]
    sfârşit dacă
    scrie „Introduceţi codul operaţiei:”
    citeşte cod
sfârşit cât timp

Arbori de intervale