Clasele 11-12 lecția 7 - 29 oct 2014

From Algopedia
Jump to: navigation, search

Arbori indexați binar

Un arbore indexat binar (AIB, în engleză binary indexed tree, BIT sau Fenwick tree) este o structură de date care tratează eficient următoarele operații pe un șir de numere:

  • adaugă(val, x): adaugă val la poziția x;
  • suma(x, y): calculează suma valorilor între pozițiile x și y inclusiv.

Menționăm în treacăt două metode naive:

  • Vector de valori: atunci adaugă() durează O(1), dar suma() durează O(n).
  • Vector de sume parțiale: atunci suma() durează O(1), dar adaugă() durează O(n) (deoarece v[x] apare în sumele parțiale s[x] ... s[n]).

Arborii indexați binar răspund la ambele operații în O(log n). Puteți citi și articolul original al lui Fenwick.

Stocare

Un AIB necesită un singur vector, să zicem aib[]. Fiecare element din vector stochează suma unei subsecvențe terminată pe acea poziție:

  • pozițiile impare stochează suma unui singur element (elementul însuși);
  • pozițiile pare stochează suma ultimelor două elemente;
  • pozițiile divizibile cu 4 stochează suma ultimelor 4 elemente;
  • pozițiile divizibile cu 2k stochează suma ultimelor 2k elemente.

Poziția 0 este nefolosită într-un AIB. Este una din rarele situații când irosim acea poziție, deoarece operațiile pe biți despre care vom discuta se complică inutil dacă insistăm să folosim și poziția 0.

Iată un tabel care arată sumele stocate pe fiecare poziție.

poziția 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
memorează suma valorilor 1 1 - 2 3 1 - 4 5 5 - 6 7 1 - 8 9 9 - 10 11 9 - 12 13 13 - 14 15 1- 16 17 17 - 18 19 17 - 20 ...

De exemplu, iată un vector v și valorile AIB corespunzătoare.

poziția 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
v 2 5 1 0 4 8 6 3 2 7 5 4 1 2 8 3 0 2 9 5 ...
aib 2 7 1 8 4 12 6 29 2 9 5 18 1 3 8 61 0 2 9 16 ...

În general, dimensiunea unui AIB este o putere a lui 2.

Calcularea sumei

Suma intervalului [x, y] se poate calcula ca diferența sumelor parțiale [1, y] și [1, x - 1]. De aceea, de acum încolo ne vom preocupa doar de sume parțiale.

Suma parțială [1, x] se poate calcula exprimându-l pe x ca sumă de puteri ale lui 2. Astfel, 46 = 32 + 8 + 4 + 2, astfel încât suma intervalului [1, 46] se poate scrie ca

aib[46] + aib[44] + aib[40] + aib[32]

Într-adevăr, aib[46] reține suma intervalului [45, 46], apoi aib[44] reține suma intervalului [41, 44] etc.

De aceea, pseudocodul este:

  int suma(int x) {
    int s = 0;
    while (x) {
      s += aib[x];
      p = cea mai mică putere a lui 2 din descompunerea lui x
      x -= p;
    }
    return s;
  }

Din lecția trecută, știm metoda Kernighan de a elimina cel mai puțin semnificativ bit din reprezentarea binară a lui x. Codul C este:

  int suma(int x) {
    int s = 0;
    while (x) {
      s += aib[x];
      x &= x - 1;
    }
    return s;
  }

Modificarea unei valori

Când adăugăm val la poziția x, trebuie să actualizăm toate sumele parțiale care conțin poziția x. Care sunt acestea? Fie x = 101110002 (nici nu ne interesează cât face aceasta în baza 10). Știm că la dreapta lui x se află:

  • Diverse poziții impare, de exemplu 10111001. Acestea nu ne interesează, deoarece merg înapoi doar un element și nu ajung până la x.
  • Diverse poziții divizibile cu 2, de exemplu 10111010. Acestea nu ne interesează, deoarece merg înapoi doar 2 elemente și nu ajung până la x.
  • Diverse poziții divizibile cu 4, de exemplu 101111000. Acestea nu ne interesează, deoarece merg înapoi doar 4 elemente și nu ajung până la x.
  • Diverse poziții divizibile cu 8. Acestea ne interesează! Care este următoarea poziție divizibilă cu 8? Este 11000000, care merge înapoi 64 de elemente, până la 10000001, deci conține poziția x.
  • Dar după aceea? Aplicăm același argument și deducem că următoarea poziție interesantă este 100000000, care merge înapoi 256 de elemente.
  • Continuăm până când depășim lungimea AIB-ului.
  void adaugă(int val, int x) {
    do {
      aib[x] += val;
      p = cea mai mică putere a lui 2 din descompunerea lui x
      x += p;
    } while (x <= aibSize);
  }

Avem și o metodă de manipulare a biților care să izoleze cel mai puțin semnificativ bit din reprezentarea binară a lui x, pe care apoi îl adăugăm la x. Codul C este:

  void adaugă(int val, int x) {
    do {
      aib[x] += val;
      x += x & -x;
    } while (x <= aibSize);
  }

Găsirea unei valori punctuale

Pentru a găsi valoarea pe o singură poziție x, o putem calcula în O(log n) ca pe suma(x) - suma(x - 1). Dar există și o implementare în O(1) amortizat.

Să considerăm poziția x = 60. Dacă o calculăm prin diferența sumelor parțiale, obținem

val(60) = suma(60) - suma(59) = (aib[60] + aib[56] + aib[48] + aib[32]) - (aib[59] + aib[58] + aib[56] + aib[48] + aib[32])

Se vede că, de la poziția 56 încolo, sumele de intervale se anulează în cele două paranteze. Nu este o coincidență. Fie:

x     = bbb...bbb10000
x - 1 = bbb...bbb01111

, unde b sunt niște biți oarecare. Este vizibil că, în calculul sumelor parțiale, atât x cât și x - 1 vor elimina biți de 1 de la coadă până vor ajunge la strămoșul comun, care este

p     = bbb...bbb00000

De aceea, codul C este:

  int val(int x) {
    int s = aib[x];
    int parent = x & (x - 1);
    x--;
    while (x != parent) {
      s -= aib[x];
      x &= x - 1;
    }
    return s;
  }

De ce este importantă această abordare? Nu este ea tot logaritmică? Nu! Dacă distribuția lui x este aleatoare, atunci complexitatea este O(1). Să remarcăm că jumătate din valorile din AIB (pozițiile impare) stochează chiar valoarea acelei poziții, deci funcția val() va face o singură iterație. Încă un sfert vor avea de curățat un singur bit 1, deci vor face două iterații. Încă o optime vor face trei iterații. Media acestor costuri converge la 2.

Căutarea binară a unei sume parțiale

Ocazional avem nevoie să căutăm cea mai mare poziție x pentru care suma intervalului [1, x] nu atinge o valoare dată val. Desigur, problema are sens doar dacă elementele structurii sunt nenegative, astfel încât sumele parțiale să fie nedescrescătoare. Putem face o căutare binară naivă. Aceasta necesită O(log n) pași, iar la fiecare pas suma parțială până în acel punct se calculează în O(log n) pași. Așadar, complexitatea naivă este O(\log ^{2}n).

O abordare mai eficientă procedează astfel.

  • Măsoară suma parțială la jumătatea AIB-ului. Aceasta se face în O(1), căci aib[n/2] este chiar suma parțială a intervalului [1, n/2], presupunând că n este o putere a lui 2.
  • Dacă suma parțială este prea mare, reia căutarea de la n/4
  • Dacă suma parțială este prea mică, o scade din valoarea căutată și reia căutarea de la 3n / 4.
  • În general, după primii k pași, algoritmul reduce intervalul de căutat de 2k ori.
  int cautăSP(int val) {
    int x = 0;
    int interval = n / 2;
    while (interval) {
      if (aib[x + interval] < val) {
        val -= aib[x + interval];
        x += interval;
      }
      interval >>= 1;
    }
    return x;
  }

Iată un exemplu:

poziția 1 2 3 4 5 6 7 8
v 6 2 4 0 0 0 1 3
sumele parțiale 6 8 12 12 12 12 13 16
aib 6 8 4 12 0 0 1 16
  • Căutăm suma 12. Dorim ca algoritmul să returneze 2 (cea mai mare poziție pentru care suma parțială nu atinge valoarea 12).
  • Algoritmul pornește cu x = 0, interval = 4.
  • aib[4] = 12, prea mare. Înjumătățim intervalul, obținem interval = 2
  • aib[2] = 8 < 12. Adăugăm intervalul la x, obținem x = 2. Înjumătățim intervalul, obținem interval = 1.
  • aib[3] = 12, prea mare. Înjumătățim intervalul, obținem interval = 0
  • Returnăm x = 2.

Formularea problemei este importantă. Ne-ar fi mai greu să găsim cea mai mică poziție x pentru care suma intervalului [1, x] atinge o valoare dată val. În exemplul de mai sus, suma parțială la poziția 4 este 12, dar nu putem afla cu ușurință dacă și poziția 3 întrunește această condiție.

Aplicații

Frecvențe de 1 și 0

O aplicație frecventă este întreținerea unor informații booleene:

  • setează al k-lea element pe 1 (sau pe 0)
  • spune-mi câte elemente de 1 există între x și y.

Codificarea permutărilor, despre care am vorbit ora trecută, necesită AIB pentru o complexitate de O(n log n).

Actualizări pe interval

Discuție liberă: Cum putem extine AIB ca să admită în O(log n) și operația

  • adaugă(val, st, dr): adaugă val pe toate pozițiile dintre st și dr inclusiv

Arbori 2-D (și k-D)

Discuție liberă: Cum putem răspunde la aceleași întrebări pe o matrice? Dorim timp O(\log ^{2}n).

  • Cu ce trebuie să înlocuim segmentele de 1 x 2p?

Probleme

  • Problema Costume acceptă o soluție simplă în O(n log n) bazată pe AIB (dar există și o soluție în O(n) -- căutați-o!)
  • Problema Inversiuni acceptă o soluție simplă cu AIB (dar și una frumoasă cu un mergesort modificat).
  • Nu uitați și de pagina de căutat probleme de la Infoarena.

Temă