05-rmq.tex

\include{header}

\begin{document}


\begin{frame}
  \titlepage
\end{frame}


\begin{frame}[fragile]
\frametitle{Range Minimum Query}
\begin{block}{Input}
\begin{itemize}
\item
Array $A$ di $n$ interi
\item
Indicizzare $A$ in tempo $O(n \log n)$
\end{itemize}
\end{block}
\begin{block}{Query}
\begin{itemize}
\item
Dati due interi $i, j$, $1\le i\le j\le n$, calcolare $\min_{i\le z\le j}A[z]$ in tempo $O(1)$.
\end{itemize}
\end{block}
\end{frame}

\begin{frame}[fragile]
\frametitle{Indice}
\begin{itemize}
\item
Array $B[x,y] = \min_{x\le z < x+2^{y}}A[z] $
\item
$B[x,0] = A[x] $
\item
$B[x,y] = \min \left\{ B[x,y-1], B[x + 2^{y-1},y-1] \right\}$, se $y>0$
\item
$n \lceil  \log_{2} n \rceil$ elementi
\item
$w\gets \lfloor   \log_{2} (j-i+1) \rfloor$, $w$ è la più grande potenza di $2$ che è minore o uguale
a $j-i+1$
\item
$\min_{i\le z\le j}A[z] = \min \{ B[i, w], B[j - 2^{w} + 1, w]\}$
\end{itemize}
\end{frame}




\begin{frame}[containsverbatim]\frametitle{Licenza d'uso}
  \small

  Quest'opera {\`e} soggetta alla licenza Creative Commons:
Attribuzione-Condividi allo stesso modo 4.0.
  (\verb+https://creativecommons.org/licenses/by-sa/4.0/+).

Sei libero di riprodurre, distribuire, comunicare al pubblico, esporre
in pubblico, rappresentare, eseguire, recitare e modificare quest'opera
alle seguenti condizioni:
\begin{itemize}
\item
Attribuzione — Devi attribuire la paternit{\`a} dell'opera nei modi
indicati dall'autore o da chi ti ha dato l'opera in licenza e in modo tale da
non suggerire che essi avallino te o il modo in cui tu usi l'opera.
\item
Condividi allo stesso modo — Se alteri o trasformi quest'opera, o se
la usi per crearne un'altra, puoi distribuire l'opera risultante solo con
una licenza identica o equivalente a  questa.
\end{itemize}
%  \vspace*{1cm}
\end{frame}

\end{document}