Konstantna struktura

Problem

Potrebno je dizajnirati strukturu koja pamti niz brojeva i koja sto brze moze odgovoriti na upit:

koji je najmanji broj u intervalu [lo, hi]?

Npr, za niz brojeva:

0	1	2	3	4	5	6	7
-1	1	4	2	-5	1	2	3

Mozemo navesti sljedeće upite i odgovore:

[0, 2] : -1
[0, 7] : -5
[2, 5] : -5
[5, 7] : 1
[2, 2] : 4

Primjetite da nikada ne tražimo promjenu vrijednosti na nekom polju već samo izvršavamo operacije čitanja. Brojevi su numerirani od 0 za potrebe kasnijih odjeljaka.

Razmatranja

Važno svojstvo funkcije min koje ćemo koristiti jest sljedeće:

Koje možda izgleda malo nerazumljivo kada je napisano, ali je zapravo krajnje jednostavno. Uzmimo dva skupa elemenata i . Neka je najmanji element u , a najmanji element u . Manji od brojeva i je sigurno najmanji element u .

U našem problemu će se to odnositi na intervale brojeva. Kako bi pronašli najmanji broj u intervalu od npr. 6 do 8, promatrati ćemo intervale [6, 7] i [7, 8]. Bez obzira što se ova dva intervala preklapaju, ako uzmemo manji broj od rješenja u ta dva intervala sigurni smo da imamo najmanji broj u cijelom intervalu.

Predračunanje (engl. preprocessing)

U fazi inicijalizacije strukture cilj nam je unaprijed izračunati najmanje vrijednosti elemenata u nekim intervalima da bi kasnije mogli što brže doći do najmanje vrijednosti za bilo koji interval. Koristiti ćemo intervale čija je veličina potencija broja dva.

int mins[kLogMaxN][kMaxN];

U nizu mins[ a ][ b ] piše najmanji broj iz intervala . Kada je tj. u prvom retku ovog polja, nalaze se originalni članovi niza jer je tada i desna granica intervala je isključiva. Ex:

Prema tome, za početak sve brojeve iz niza možemo učitati u prvi redak matrice mins.

void load() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &mins[0][i]);
  }
}

Da bi izračunali vrijednost u polju mins na nekom višem retku, odnosno najmanji broj u intervalu neke veće potencije broja dva, možemo se poslužiti sljedećom relacijom:

mins[a + 1][b] = min(mins[a][b], mins[a][b + (1 << a)]);

Odnosno, najmanji broj u intervalu veličine koji počinje na mjestu možemo dobiti tako da promatramo intervale veličine koji počinju na mjestima i . Ta dva intervala se zajedno spoje u veliki interval čije rješenje tražimo i ako uzmemo manji od najmanjih brojeva u njima, dobili smo najmanji broj u velikom intervalu. Primjer:

0	1	2	3	4	5	6	7
-1	1	4	2	-5	1	2	3

Najmanji broj u intervalu dok je najmanji broj u intervalu . Najmanji broj u velikom intervalu

Stoga preprocessing možemo napraviti dinamički:

void init() {
  for (int pot = 0; (1 << pot) <= n; ++pot) {
    for (int i = 0; i < n; ++i) {
      mins[pot + 1][i] = min(
        mins[pot][i],
        i + (1<<pot) < maxn ? mins[pot][i + (1<<pot)] : INF
      );
    }
  }
}

Operator << je lijevi posmak broja u binarnom zapisu pa je operacija 1 << x efektivno . INF predstavlja pozitivnu beskonačnost.

Upit

I naposljetku, upit za najmanji broj u bilo kojem intervalu neće biti teško implementirati jednom kada je predračunanje napravljeno. Neka je traženi interval veličine .

Potrebno je pronaći najveću potenciju broja dva manju ili jednaku od . Neka je to .

Primjetite da intervali i sigurno uključuju cijeli interval . U to se možemo uvjeriti uspoređujući njihovu ukupnu duljinu sa duljinom originalnog intervala:

Jer bi u suprotnom tražena potencija broja dva bila barem za jedan veća!

Uz pronađeni rješenje za najmanji broj u intervalu je min(mins[i][a], mins[i][b - (1<<i)]).

Ostaje pitanje kako pronaći najveću potenciju broja 2 manju ili jednaku nekom broju . Budući da je najveći za koji nas ovo zanima upravo broj članova u nizu, i za ovu vrijednost možemo napraviti predračunanje u istoj složenosti!

void init2() {
  najveca_pot[1] = 0; // 2^0 <= 1, dok 2^1 nije
  for (int i = 2; i < maxn; ++i)
    najveca_pot[i] = najveca_pot[i/2] + 1;  
}

Zaključak

Postoji struktura podataka koja uz vremena predračunanja može odgovoriti na pitanje najmanjeg broja u intervalu u konstantnom vremenu.

Funkcija upita izgleda ovako:

int query(int a, int b) {
  int naj_pot = najveca_pot[b - a];
  return min(mins[naj_pot][a], mins[naj_pot][b - (1 << naj_pot)]);
}

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License