Problema (initiala)
Implementarea eficienta a urmatoarelor operatii definite pe un array de numere A[1..N] :
• update(pos, val) : A[pos] += val;
• query(l, r) : sum(A[l], A[l+1], ... A[r]) = ?
Numita si "Partial-Sums Problem"
Solutii suboptimale
• naiv : update O(1), query O(N)
• 'smenul lui Bogdan Batog'
impartire 'bucati' sqrt(N):
precalcularea sumelor pe intervale de lungime constanta
O(K + N / K) per update & query, minim pentru k = sqrt(N)
O(sqrt(N)) = O(N0.5)
0 1 2 3 4 5 6 7 8 9 0 1 2A[]
S[] 0 1 2 3 4
Arbori indexati binar
• idea e tot precalcularea sumelor pe intervale, dar pe alta structura
• intervalele nu sunt disjuncte si au lungimi diferite
• convenabil pentru implementare si eficient pentru complexitate:
– pentru implementare : structura se poate retine tot intr-un array care se poate itera usor
– pentru complexitate : numarul maxim de intervale in care se afla un element e logaritmic si orice interval e reuniunea a unui numar logaritmic de intervale
Arbori indexati binar - structura
• fiecare element retine suma pe un interval:
• N intervale in total
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Arbori indexati binar - structura
• pozitiile impare retin intervale de lungime 1, formate din pozitia respectiva
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Arbori indexati binar - structura
• pozitiile pare nedivizibile cu 4 retin intervale de lungime 2 ce au capat dreapta pe pozitia respectiva
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Arbori indexati binar - structura
• pozitiile divizibile cu 4 si nu cu 8 ... intervale de lungime 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Arbori indexati binar - structura
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
• in general pozitia k retine intervalul [k-2p+1, k]unde 2p este cea mai mare putere a lui doi cu care se divide k
Arbori indexati binar : query(l, r)
• query(l, r) =
= A[l] + A[l+1] + ... + A [r]
= A[1] + A[2] + ... + A[r] - (A[1] + A[2] + ... + A[l-1])
= sum(1, 2, .. r) - sum(1, 2, ... l-1)
= query(r) - query(l-1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
r >= l
Arbori indexati binar : query(1...p)
Exemplu:
• p = 13
• A[1] + ... + A[13] = S[13] + S[12] + S[8]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
p
Arbori indexati binar : query(1...p)
• p = 13
• A[1] + ... + A[13] = S[13] + S[12] + S[8]
• 13 - 1 = 12
12 - 4 = 8
8 - 8 = 0 stop
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
p
la fiecare pas se scade cea mai mare putere a lui doi cu care se divide pozitia curenta, conform structurii intervalelor
Arbori indexati binar : query(1...p)
Implementare:
powTwo(pi) = cea mai mare putere a lui doi cu care se divide pi.
Arbori indexati binar : query(1...p)
Implementare:
powTwo(pi) = cea mai mare putere a lui doi cu care se divide pi.
Arbori indexati binar : powTwo(p)
Exemplu: powTwo
= 11010011000(2) = 1688(10)= 11010010111
= 00000001111
= 00000001000(2) = 8(10)
pi
pi-1
pi^(pi-1)
pi^(pi-1)&pi
1688 / 8 = 211
alternativ : (pi & -pi)
Arbori indexati binar : update(p, val)
• update(p, val) trebuie sa faca incrementarea cu val pentru toate pozitiile care mentin intervale ce includ pozitia p
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Arbori indexati binar : update(p, val)
• Exemplu p = 10
• S[10] += val S[12] += val S[16] += val
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
p
Arbori indexati binar : update(p, val)
• Exemplu p = 10
• S[10] += val S[12] += val S[16] += val
• 10 + 2 = 12
12 + 4 = 16
16 + 16 = 32 > 19 stop
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
la fiecare pas se adauga cea mai mare putere a lui doi cu care se divide pozitia curenta, conform structurii intervalelor
Arbori indexati binar : complexitate
• query(...) si update(...) au aceeasi analiza
– itereaza de la p la 0 sau de la p la N
– lungimea 'saltului' se dubleaza cel putin la fiecare pas
– deci O(logN) per operatie
Arbori indexati binar : upper bounds
• naiv : O(N)
• bucati radical N : O(N0.5)
• AIB : O(logN)
• Se poate mai rapid?
• Se poate demonstra ca nu se poate mai rapid? :)
Lower & Upper bounds
• Lower bound defineste cea mai 'mare' complexitate despre care s-a demonstrat ca mai rapid de atat nu se poate rezolva problema
• Upper bound defineste cea mai 'mica' complexitate pentru care s-a descoperit algoritm care rezolva problema
• Ideal Lower bound = Upper bound, atunci problema este inchisa
Arbori indexati binar : lower bounds
• Arbori de intervale : 1977
• AIB : 1994
• SODA 2004 : Tight bounds for the partial-sums problem, Mihai Pătrașcu, Erik D. Demaine, MIT
Arbori indexati binar - final
• Arhiva educationala infoarena:http://www.infoarena.ro/problema/aib
• Articol Topcoder:http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
• Articol GInfo:http://www.ginfo.ro/revista/13_1/focus.pdf
Operatii si Complextitate
Timp :
• Update O(log N)
• Range Update O(log N)
• Query O( log N)
Memorie : O(N)
Se extind cu usurinta pentru spatii N-dimensionale
Problema 1
• Un vector de N numere si urmatoareleoperatii :
– Schimba valoarea unui element
– Interogarea minumului pe orice interval
• Putem folosi arbori intexari binar ?
– daca da: cum? daca nu: de ce?
Detalii de implementare
• 2 functii cu 5 parametri (se poate reduce la 3)
– update(nod, st, dr, a, b);
– query(nod, st, dr, a, b);
Detalii de implementare
update(nod, st, dr, a, b) {daca (a <= st) si (dr <= b) atunci {
modifica structura auxiliara din nod } altfel {
mij = (st + dr) / 2daca (a <= mij) atunci
update(2 * nod, st, mij, a, b)daca (b > mij) atunci
update(2 * nod + 1, mij + 1, dr, a, b)
actualizeaza structura auxiliara din nodul nod// in functie de copii
}}
Detalii de implementare
query(nod, st, dr, a, b) {daca (a <= st) si (dr <= b) atunci {
returneaza structura auxiliara din nod} altfel {
mij = (st + dr) / 2daca (a <= mij) atunci
query(2 * nod, st, mij, a, b)daca (b > mij) atunci
query(2 * nod + 1, mij + 1, dr, a, b)
returneaza (structura auxiliara din apelulstang combinata cu cea din apelul drept)
}}
Detalii de implementare
• Pentru simplitate se aloca un vector de dimensiune maxim 4 * N
• Codificarea legaturilor (indexare de la 0):
– nod * 2, fiul stanga
– nod * 2 + 1, fiul dreapta
– nod / 2 , parinte
Problema 2
• Un vector de N numere si urmatoareleoperatii :
– Schimba valoarea elementelor unei secvente
– Interogarea minimului pe orice interval
Lazy propagation
• Range update
– In loc sa modificam valoarea unui singur element, modificam valoarea tuturor elementelor dintr-o subsecventa
– Cum ramanem la O(log N ) ?
Top Related