Implementarea eficienta a urmatoarelor operatii definite...

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 naive

• naiv : update O(1), query O(N)

• invers este posibil? cum?

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

binary indexed tree

Fenwick tree

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


• 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


• 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


• 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


• ...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19


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


• 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


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


• 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


• 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


aproape identic cu implementarea query(...)

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

http://www.infoarena.ro/problema/aib

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

http://www.ginfo.ro/revista/13_1/focus.pdf

Arbori de intervale(Segment Trees)

Structura

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?

Problema 1

• Fie N = 12

• Sirul 3, 5, 1, 7, 9, 10, 3, 7, 2, 1, 5, 6

(indexare de la 0 la N-1)

Problema 1

0 1 2 3 4 5 6 7 8 9 10 11

3 5 1 7 9 10 3 7 2 1 5 6

valoarea nodurilor frunza

Problema 1

0 1 2 3 4 5 6 7 8 9 10 11

3 5 1 7 9 10 3 7 2 1 5 6

valoarea nodurilor interne

Query

query(5, 7) : min(A[5], A[6], A[7]) = ?

Update

update: a[5] = -1

se modifica nodul frunza

Update

update: a[5] = -1

si (eventual) parintii acestuia

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);


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

}}


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)

}}


• 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 ) ?

Lazy propagation

Lazy propagation

update(0, 2, 6)a[0] = a[1] = a[2] = 6

Lazy propagation

ulterior ... un eventualquery(1, 1)

Aplicatii

• Geometrie

• RMQ cu update

• Interogari pe intervale

Implementare

• Arhiva educationala infoarena

– AIB

– AI

• HackerCup

Implementarea eficienta a urmatoarelor operatii definite...

Documents

Transcript of Implementarea eficienta a urmatoarelor operatii definite...