Zobrazenie zdroja stránky RMQ a LCA

'''Predbežná verzia poznámok, nebojte sa upravovať: pripojiť informácie z prezentácie, preložiť do slovenčiny, pridať viac vysvetľujúceho textu a pod.'''

==LCA, RMQ==
* intro on slides
[[Image:lca1.png]]

===LCA via RMQ===
* zname algoritmy a triv. algoritmy na slajde
* definicia poli V, D, R + ich vytvorenie slajdy
* assume that LCA(u,v) = x (fig.) and that R[u]<=R[v]
** tree traversal visits x, then subtree with u, then again x, then subtree with v, then again x, and only after that it can get above x
** D[x] = min D[R[u]..R[v]] (for R[u]<=R[v])
** this holds even if LCA(u,v)=u or v
** if we can quickly find k = arg min_k in {i..j} D[k], the result is V[k]
* we have trasformed LCA to a new problem

===Range minimum query RMQ===
* goal: preprocess array A so that we can any two indices i and j quickly find index of minimum in A[i..j]
* Alg 1: no preprocessing, O(n) query: find minimum in interval
* Alg 2: O(n^2) preprocessing, O(1) query: precompute for all (i,j) in a table
* Alg 3: O(n log n) preprocessing, O(1) query: store minimum only for intervals of length 2^k
** M[i,k]: index of minimum in A[i..i+2^k-1] for k=1,2,...,floor(log n)
<pre>
i    0  1  2  3  4  5  6  7  8  9 10 11 12
A[i] 0  1  2  1  2  3  2  1  0  1  0  1  0
--------------------------------------------
k=1  0  1  3  3  4  6  7  8  0 10 10 12  -
k=2  0  1  3  3  7  8  8  8  8 10  -  -  -
k=3  0  8  8  8  8  8  -  -  -  -  -  -  -
</pre>
** Preprocessing M[i,k]: if A[M[i,k-1]]<A[M[i+2^{k-1},k-1]] then M[i,k]=M[i,k-1], else M[i,k]=M[i+2^{k-1},k-1]
** RMQ(i,j): 
*** let k=floor(log_2(j-i+1)) (max size of a block inside A[i..j]), floor(log x) can be precomputed for i=1..n
*** if A[M[i,k]]<A[M[j-2^k+1,k]] return M[i,k] else return M[j-2^k+1,k] (figure of overlapping intervals)

===+-1RMQ===
* v poli D pre LCA plati, ze susedne cisla sa lisia o 1 D[i]-D[i+1] in {-1,1}
* Ukazeme si lepsi RMQ pre polia majuce tuto vlastnost, tento problem volame +-1RMQ
* rozdelime A na bloky velkosti m = log_2 n/2
* v kazdom bloku najdeme minimum, minima dame do pola A'[0..n'-1] a polohu tychto minim do pola M'[0..n'-1] kde n' = n/m = 2n/log_2 n
** pole A' predspracujeme pomocou alg 3 v case O(n'log n') = O(n)
* pri RMQ uvazujeme dva pripady (obrazok): 
** i a j v roznych blokoch (bi a bj)
*** spocitaj RMQ v A'[bi+1..bj-1] O(1)
*** spocitaj minimum v bloku bi od i po koniec bloku (neskor)
*** spocitaj minimum v bloku bj od zaciatku bloku po j (neskor)
*** najdi minimum tychto troch cisel
** i a j v tom istom bloku
*** spocitaj minimum medzi dvoma indexami v ramci bloku
* potrebujeme teda rieisit +-1RMQ v ramci blokov
**reprezentacia bloku: prvy prvok + rozdiely medzi susedmi, napr 2,3,2,1 -> 2,+1,-1,-1
**na urcenie polohy minima nepotrebujeme vediet prvy provok, staci iba m-1 rozdielov +1,-1,-1
**kazdy blok sa teda da zapisat ako binarne cislo s m-1 bitmi
**najviac 2^{m-1}<=sqrt(n) roznych typov blokov
**pre kazdy typ predpocitaj vsetky odpovede (alg. 2) v case O(m^2)
**spolu teda O(2^{m-1} m^2) = O(sqrt(n)*log(n)^2) = o(n)

+-1RMQ predpracovanie:
* spocitaj typ kazdeho bloku, uloz do pola O(n)
* pre kazdy typ spocitaj odpovede o(n) (v priemere sa jeden typ opakuje cca sqrt(n) krat, takze usetrime)
* spocitaj pole A' O(n)
* predpsracuje pole A' O(n)
spolu O(n)

RMQ(i,j):
* 2x minimum v bloku O(1)
* 1x minimum v A' O(1)
spolu O(1)

LCA predspracovanie:
* prehladanie stromu a vytvorenie poli O(n)
* +-1 RMQ predspracovanie O(n)

LCA(u,v)
2 pristupy do pola R, +-1RMQ na poli D, pristup do pola V O(1)

===RMQ===
[[Image:lca2.png]]

* vieme teda dobre riesit +-1RMQ a pomocou neho aj LCA
* vseobecne RMQ vieme riesit pomocou LCA
* z pola A vytvorime karteziansky strom:
** v koreni ma polohu i najmensieho cisla 
** v lavom podstrome rekurzive definovany strom pre cast pola a[0..i-1]
** v pravom podstrome rekurzivne definovany strom pre cast pola a[i+1..n]
* strom sa da vytvorit v O(n):
** ak uz mame strom pre a[0..i-1] a pridavame a[i], a[i] bude niekde na najpravejsej ceste
** ideme zo spodu po tejto ceste a najdeme prvy vrchol j, pre ktory a[j]<a[i]
** i dame ako prave dieta j, stare prave dieta j dame ako lave dieta i
** kazdy vrchol raz pridame do cesty a raz uberieme (vsetky vrcholy, ktore sme presli pri hladani j uz nie su na pravej ceste), teda celkovo O(n)
** potential function: number of vertices on the rightmost path
* RMQ(i,j) = LCA(ij)
** vezmime si uplne minimum v poli na poz. k: pre ktore dvojice bude vyslekodm RMQ(i,j)?
** pre tie, kde i<=k, j>=k, pre tieto je k aj LCA
** ostatne dvojice su bude uplne nalavo od k alebo uplne napravo, tam je strom definovany rekurzivne a teda tiez funguje

===Print small===
* mame pole cisel A, predspracovane ore RMQ
* chceme vypisat vsetky indexy k in {i..j} take ze A[i]<=x
<pre>
void small(i,j,x) {
  if(j>i) return;
  k = rmq(i,j);
  if(a[k]<=x) { 
    print k;
    small(i,k-1);
    small(k+1,j);
  }
}
</pre>
* analyzujte cas vypoctu vzhladom na p, kde p je pocet vypisanych indexov