Potrebno je dizajnirati strukturu koja pamti niz brojeva i koja sto brze moze odgovoriti na upit:
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:
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.
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.
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.
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; }
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