%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%----------------------------------------------------------------------------------------
%	PACKAGES AND THEMES
%----------------------------------------------------------------------------------------


\documentclass[xcolor=dvipsnames]{beamer}

\mode<presentation> {

% The Beamer class comes with a number of default slide themes
% which change the colors and layouts of slides. Below this is a list
% of all the themes, uncomment each in turn to see what they look like.

\usepackage{hyperref}
\usepackage{mathtools}
%\usetheme{default}
%\usetheme{AnnArbor}
%\usetheme{Antibes}
%\usetheme{Bergen}
\usetheme{Berkeley}
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{CambridgeUS}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
%\usetheme{Dresden}
%\usetheme{Frankfurt}
%\usetheme{Goettingen}
%\usetheme{Hannover}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
%\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto}
%\usetheme{Pittsburgh}
%\usetheme{Rochester}
%\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}

% As well as themes, the Beamer class has a number of color themes
% for any slide theme. Uncomment each of these in turn to see how it
% changes the colors of your current slide theme.

%\usecolortheme{albatross}
%\usecolortheme{beaver}
%\usecolortheme{beetle}
%\usecolortheme{crane}
%\usecolortheme{dolphin}
%\usecolortheme{dove}
%\usecolortheme{fly}
%\usecolortheme{lily}
%\usecolortheme{orchid}
%\usecolortheme{rose}
%\usecolortheme{seagull}
%\usecolortheme{seahorse}
%\usecolortheme{whale}
%\usecolortheme{wolverine}

%\setbeamertemplate{footline} % To remove the footer line in all slides uncomment this line
\setbeamertemplate{footline}[page number] % To replace the footer line in all slides with a simple slide count uncomment this line

}

\usepackage{listings}
\usepackage{color}





\usepackage{float}
\usepackage{xcolor}
\usepackage{amsmath}
\usepackage{tikz}
\usetikzlibrary{calc, arrows}
\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
%\usepackage {tikz}
\usepackage{tkz-graph}
\GraphInit[vstyle = Shade]
\tikzset{
  LabelStyle/.style = { rectangle, rounded corners, draw,
                        minimum width = 2em, fill = yellow!50,
                        text = red, font = \bfseries },
  VertexStyle/.append style = { inner sep=5pt,
                                font = \normalsize\bfseries},
  EdgeStyle/.append style = {->, bend left} }
\usetikzlibrary {positioning}
\usetikzlibrary{arrows}
%\usepackage {xcolor}
\definecolor {processblue}{cmyk}{0.96,0,0,0}

\newcommand{\abs}[1]{\lvert #1 \rvert}


\lstdefinestyle{mystyle}{
    commentstyle=\color{olive},
    keywordstyle=\color{blue},
    numberstyle=\tiny\color{gray},
    stringstyle=\color{violet},
    basicstyle=\ttfamily\footnotesize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=2
}

\lstset{style=mystyle}

%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\title{Range queries} % The short title appears at the bottom of every slide, the full title is only on the title page

\author{Gilles Englebert} % Your name
\institute{Slides at englebert.lu}
\date{\today} % Date, can be changed to a custom date

\DeclareMathOperator{\rsq}{RSQ}
\DeclareMathOperator{\rmq}{RMQ}
\DeclareMathOperator{\lca}{LCA}

\begin{document}


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

\begin{frame}
\frametitle{Overview}
\tableofcontents
\end{frame}

%----------------------------------------------------------------------------------------
%	PRESENTATION SLIDES
%   This content is under GPL3 license by Gilles Englebert
%----------------------------------------------------------------------------------------

\section{Range queries}
\begin{frame}{Task}
\textbf{Situation:} Let $a[1\dots n]$ be an array of integers. \pause Say we need to compute, for $i<j$, \textbf{range sum queries} (e.g. running average of temperatures):
\begin{displaymath}
\rsq(i,j) := \sum_{k=i}^{j} a[k] = a[i] + \dots + a[j],
\end{displaymath}
\pause or \textbf{range minimum queries} (e.g. minimum elevation in part of a map): 
\begin{displaymath}
\rmq(i,j) := \min(a[i], \dots, a[j]).
\end{displaymath}
We need to repeat these computations many times for different choices of $i,j$.
\end{frame}

\begin{frame}
These are multiple different problems, depending on whether we are in the:  \newline
\pause
\begin{itemize}
\item \textbf{Static problem}: $a[1\dots n]$ is fixed. \pause
\item \textbf{Dynamic problem}: $a[1 \dots n]$ can be updated in between queries.
\end{itemize}
\pause

It also depends on the binary operation that we consider, $a+b$ is fundamentally different from $\min(a,b)$. For example, addition has an \textit{inverse operation}, namely $-$, which $\min$ does not have. 

\end{frame}

\section{The static case}
\begin{frame}{The \textit{static} case}
Initial setup time by \textbf{precomputation} allows for faster queries. This works differently for $\rsq$ and $\rmq$. Let's begin with \textbf{sums}.
\begin{solution}
Calculate $s[k] = \sum_{i=1}^k a[i]$ for $1 \le k \le n $ in time $O(n)$. Then
\[\rsq(i, j) = s[j]-s[i-1]\]
in $O(1)$!
\end{solution}
\pause 
Here we used the fact that $-$ 'undoes' $+$. \newline
\textbf{Q:} does $\oplus$ (xor) have an inverse operation?
\pause
\newline
This is only faster since the $a[i]$ do not change. If they did and we had to recompute the $s[k]$, at least partially, and querying would take time $O(n)$ after all.
\end{frame}

\begin{frame}{Range minimum queries}
This does not work for $\min$, since we cannot 'undo' the operation. However, taking minimums is \textbf{idempotent}, meaning that $\min(a, b) = \min(a,b,b)$. \newline

\pause
We can use this idea by splitting $[1,n]$ into large intervals. Then we can take the minimum of elements in the interval $[a,b]$ by taking the minimum of a few (potentially overlapping) large intervals.

\pause
There are two ways of going about this:
\begin{itemize}
\item \textbf{Square root decomposition}
\item \textbf{Divide and conquer}
\end{itemize}
\end{frame}

\begin{frame}{Square root decomposition}
We divide the array into $k = \sqrt{n}$ blocks of size at most $k$.
\begin{figure}
\begin{displaymath}
\color{red} \fbox{8}\fbox{5}\fbox{1}
\color{brown} \fbox{5}\fbox{3}\fbox{7}
\color{blue} \fbox{2}\fbox{4}\fbox{5}
\end{displaymath}
\caption{Example with $n = 9$}
\end{figure}
\pause
For this example we can precompute in $O(n)$ the minima per block, i.e. $ s = \{1, 3, 2 \}. $
Now, when we want to compute the minimum for a range $[2,7]$ we decompose:
\begin{displaymath}
	\rmq (2, 7) = \min (a[2], s[1], a[6], a[7]) = 1. 
\end{displaymath}
\pause
We can query in time $O(\sqrt{n})$.
\end{frame}

\begin{frame}{Divide and conquer}
We can also divide a segment into two large overlapping parts. For this we calculate the minima already for all subsets of sizes $2^k \le n$ which are contained in $[1,n]$. There are $O(n\log n)$ such segments.
\pause 
\begin{solution}
Let $s[i][k]$ be $\rmq(i, i+2^k-1)$. Then we can compute it as:
\begin{align*}
s[i][0] &= a[i], \\
s[i][d+1] &= \min(s[i][d], s[\min(n-2^d, i+2^d )][d]).
\end{align*}
The RMQ problem can now be solved as follows: 
\begin{align*}
\rmq(i, j) = \min(s[i][d], s[j-2^d + 1][d])
\end{align*}
where d is the smallest integer such that $2^d\le\abs{i-j}$.
\end{solution}
\end{frame} 

\begin{frame}[fragile]{Homework - static range queries}
\begin{itemize}
	\item \href{onlinejudge.org}{UVa 507 - Jil rides again}
    \item \href{infosolympiad.lu}{CIL/LIO 2011 DF - Blocky}
\end{itemize}

\end{frame}

\section{The dynamic case}
\begin{frame}{Dynamic Range Sum}
When the $a[i]$'s can vary in-between queries, \textbf{Segment trees} allow for a solution similar the the DC approach above, but with a more efficient update routine.
\pause
Take the following array of size $8$:
\begin{displaymath}
\fbox{1}\fbox{4}\fbox{7}\fbox{2}\fbox{0}\fbox{3}\fbox{8}\fbox{1}
\end{displaymath}
We construct the following binary tree which covers, at different levels, segments of lengths $1, 2, 4$ and $8$:
\begin{figure}
\begin{tikzpicture}[nodes={draw, circle},  scale=0.6, ->]
  \node{0}
    child { node {1} 
        child {node{1}
            child{node[fill=black!10]{1}}
            child{node[fill=black!10]{4}}
            }
        child [missing]
        child{node{2}
        	child{node[fill=black!10]{7}}
            child{node[fill=black!10]{2}}
            }
        }
    child [missing]
    child [missing]
    child [missing]
    child { node {0} 
        child {node{0}
            child{node[fill=black!10]{0}}
            child{node[fill=black!10]{3}}
            }
        child [missing]
        child{node{1}
        	child{node[fill=black!10]{8}}
            child{node[fill=black!10]{1}}
            }
        };
\end{tikzpicture}
\end{figure}
\end{frame}

\begin{frame}{Querying}
Say we want to find $\rmq(3,6)$. Then we need to inspect the nodes:
\begin{figure}
\begin{tikzpicture}[nodes={draw, circle},  scale=0.6, ->]
  \node{0}
    child { node {1} 
        child {node{1}
            child{node[fill=black!10]{1}}
            child{node[fill=black!10]{4}}
            }
        child [missing]
        child{node{2}
        	child{node[fill=black!10]{7}}
            child{node[fill=red!10]{2}}
            }
        }
    child [missing]
    child [missing]
    child [missing]
    child { node {0} 
        child {node[fill=red!10]{0}
            child{node[fill=black!10]{0}}
            child{node[fill=black!10]{3}}
            }
        child [missing]
        child{node{1}
        	child{node[fill=red!10]{8}}
            child{node[fill=black!10]{1}}
            }
        };
\end{tikzpicture}
\end{figure}
This takes time $O(\log n)$, since we can usually stop early in the tree when a large segment is already precomputed.
\end{frame}


\begin{frame}{Updating}
If we want to change $a[4] = 2$, this will have an impact on the following nodes: 
\begin{figure}
\begin{tikzpicture}[nodes={draw, circle},  scale=0.6, ->]
  \node[fill=red!10]{1}
    child { node {1} 
        child {node{1}
            child{node[fill=black!10]{1}}
            child{node[fill=black!10]{4}}
            }
        child [missing]
        child{node{2}
        	child{node[fill=black!10]{7}}
            child{node[fill=black!10]{2}}
            }
        }
    child [missing]
    child [missing]
    child [missing]
    child { node[fill=red!10]{1} 
        child {node[fill=red!10]{2}
            child{node[fill=red!10]{2}}
            child{node[fill=black!10]{3}}
            }
        child [missing]
        child{node{1}
        	child{node[fill=black!10]{8}}
            child{node[fill=black!10]{1}}
            }
        };
\end{tikzpicture}
\end{figure}
This also takes time $O(\log n)$, since climb up the tree from the affected leaf towards the root, and a full binary tree has depth $\log n$.
\end{frame}

\begin{frame}{In practice}
So a segment tree consists of three components:
\begin{itemize}
    \item \textbf{construction} in $O(n)$
    \item \textbf{update} of one element in $O(\log(n))$
    \item \textbf{query} in $O(\log(n))$
\end{itemize}

Let us look at some code!

\href{https://visualgo.net/en/segmenttree}{\textbf{Link: Visualization of Segment Trees}}.
\end{frame}

\section{Lowest Common Ancestor}
\begin{frame}{Task}
We finish with an application of range minimum queries.
\begin{figure}
\begin{tikzpicture}[nodes={draw, circle,fill=blue!20},  scale=0.6, ->]
  \node{1}
    child { node[fill=black!50] {2} 
        child {node{3}}
        child {node[fill=red!20]{4}
            child{node[fill=red!50]{5}}
            child{node{6}}
            }
        child{node[fill=red!50]{7}}
            }
    child [ missing ]
    child [ missing ]
    child { node {8} 
        child{node{9}}
        child{node{10}}
        };
\end{tikzpicture}
\caption{Tree with $n=10$ vertices, $\lca(5,7) = 2$}
\end{figure}
Find the \textbf{lowest common ancestor}  $\lca(i,j)$ of two nodes $i$ and $j$.
\end{frame}

\begin{frame}{Another example}
\begin{figure}
\begin{tikzpicture}[nodes={draw, circle,fill=blue!20},  scale=1.0, ->]

 
  \node[fill=black!50]{1}
    child { node [fill=red!20]{2} 
        child {node{3}}
        child {node[fill=red!20]{4}
            child{node{5}}
            child{node[fill=red!50]{6}}
            }
        child{node{7}}
            }
    child [ missing ]
    child [ missing ]
    child { node [fill=red!20]{8} 
        child{node{9}}
        child{node[fill=red!50]{10}}
        };
        
 
\end{tikzpicture}
\caption{Tree with $n=10$ vertices, $\lca(6,10) = 1$}
\end{figure}
\end{frame}

\begin{frame}{Solution}
We reduce $\lca$ to $\rmq$ by noting that the lowest common ancestor is the node with the lowest depth that is passed in DFS between the two nodes one is concerned about.

\begin{solution}
Construct the arrays $E[1\dots 2n-1]$ (the sequence of nodes traversed in a DFS), $L[1\dots 2n-1]$ (their depths) and $H[1 \dots n]$, the first appearance in the list of the nodes. Notice that:
\[\lca(i,j) = E[\rmq_L(H[i], H[j])]\]
\end{solution}
\end{frame}

\begin{frame}{Example}
Let's execute the algorithm for the second example.
\begin{table}[h!]
\centering
\resizebox{\columnwidth}{!}{
\begin{tabular}{l | c c c c c | c c c c c | c c c c c | c c c c} 
 \hline
Index & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\
 \hline
H &  1 & 2 & 3 & 5 & 6 & 8 &11 &14 &15 & 17 & - & -& -& -& -& -& -& -& - \\ 
E & 1 & 2 & 3 & 2 & 4 & 5 & 4 & 6 & 4 & 2 & 7 &  2 & 1 & 8 & 9 & 8 & 10 & 8 & 1\\
L & 0 & 1 & 2 & 1 & 2 &3 &2 &\color{red} 3 &\color{red}2 &\color{red}1 &\color{red}2 &\color{red}1 & \color{blue}0 & \color{red}1 &\color{red} 2 &\color{red} 1 &\color{red} 2 & 1 & 0
\end{tabular}
}
\label{table:1}
\end{table}

Indeed, the vertex $1$ is the lowest common ancestor of $6$ and $10$.

\end{frame}

\section{Homework}
\begin{frame}[fragile]{Homework}
\begin{itemize}
    \item UVa 12532 - Interval Product (Segment Tree, easy)
    \item UVa 11235 - Frequent Values (Segment Tree)
    \item UVa 10938 - Flea Circus (LCA)
    \item IOI 2015 - Horses
    \item IOI 2019 - Arranging Shoes
\end{itemize}

\end{frame}

\section{References}
\begin{frame}[fragile]
\frametitle{References}
And some references (also clickable!)

\href{https://cpbook.net/}{Competitive Programming book} 

\href{https://usaco.org/}{USACO}

Also, if you have any questions, do not hesitate to write me at 
\href{mailto:gilles@englebert.lu}{gilles@englebert.lu}.

\end{frame}

\end{document}