\documentclass[a4paper]{book}
\usepackage[a4paper, top=3cm,bottom=3cm, left=3cm, right=3cm%
, paperheight=23cm
]{geometry}
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{booktabs}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{tikz}
\usetikzlibrary{positioning,calc,shapes}
\usepackage{todonotes}
\usepackage{hyperref}
\usepackage[backend=bibtex]{biblatex}
\bibliography{bibtex}

\usepackage{cleveref}
\usepackage{subcaption}
\captionsetup[subfigure]{subrefformat=simple,labelformat=simple}

\usepackage{lipsum}

\title{Advanced Data Structures}
\author{Martin Hafskjold Thoresen}
\date{\today}

\newcommand{\topics}[1]{Topics: \textit{#1}}
\newcommand{\code}[2]{\textsc{#1}$(#2)$}
\newcommand{\algo}[1]{\textsc{#1}}

\newcommand{\RMQ}{$\textsc{RMQ}$}
\newcommand{\LCA}{$\textsc{LCA}$}
\newcommand{\LA}{$\textsc{LA}$}


\newenvironment{example}[0]{{\parindent=0em \textbf{Example:}}}{\vspace{1em}}
\newenvironment{definition}[1]{{\parindent=0em \textbf{Definition} --- \emph{#1}:}}{\vspace{1em}}

\DeclareMathOperator*{\argmin}{arg\,min} % thin space, limits underneath in displays
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}

% Expectation symbol
\DeclareMathOperator*{\E}{\mathbb{E}}

\begin{document}
\maketitle

\chapter*{Introduction}
This book is a collection of notes the course \textit{Advanced Data Structures} at ETH Z\"urich, in the spring of 2017.
The chapters are arranged in the same way as the lectures, and some chapters covers material from two lectures.

\tableofcontents

\chapter{Hashing}
\topics{Universal hashing, tabulation hashing, hash tables, chaining, linear probing, cuckoo hashing.}

\section{Motivation}
Operations we need: \code{Query}{x}, \code{Insert}{x}, \code{Delete}{x},
where $x \in [\mathcal{U}]$.
$\mathcal{U}$ is called the \emph{Universe}.
We already know how to do this using Balanced Binary Search Trees (BBSTs), with $O(n)$ space and $O(\log n)$ time on all operations.
We would like to have $O(1)$ time, while still having $O(n)$ space.

\section{The Hash Function}

A \emph{Hash Function} is a function $h: [\mathcal{U}] \rightarrow [m]$ where $\mathcal{U} \gg m$.
$m$ is the table size.
Ideally, $h$ is a totally random family of hash functions, meaning there is no correlation between its input $u \in \mathcal{U}$ and $h(u)$.
However, encoding a totally random function takes $O(u \log m)$ space.

This is a problem since $n = U$, which is large.
Therefore we settle on a family $\mathcal{H}$ of hash functions of small size which is \emph{Universal}.
Universality means that the probability of two non-equal keys having the same hash value is $O(1/m)$:
\[\forall x \neq y\ P_{h \in \mathcal{H}}[h(x) = h(y)] = O(1/m)\]

\begin{example}
    $h(x) = ((a x) \mod p) \mod m$ where $0<a<p$, $p$ is prime and $p > m$ is a universal hash function.
\end{example}

\begin{definition}{k-independent}
    A family of hash functions $\mathcal{H}$ is k-independent if
    \[\forall x_1, \dots x_k\ \Pr[\bigwedge\limits_{i} h(x_i) = t_i] = O(1/m^k)\]
\end{definition}

\begin{example}
    $((ax + b) \mod p) \mod m$ is 2-independent.
\end{example}

\begin{example}
    A polynomial of degree $k$,
    $((\sum\limits_{i=0}^{k-1} a_i x^i)\mod p) \mod m$, is k-independent.
\end{example}

\section{Simple Tabulation Hashing}

Tabulation hashing is a hashing scheme.
We view $x$ as a vector of bit blocks $x_1, \dots, x_c$,
and use a totally random hash table on \emph{each} block.
Then we \texttt{xor} the blocks together to get the final value:
\[h(x) = T_1(x_1) \oplus T_2(x_2) \oplus \dots \oplus T_c(x_c)\]
Since a block is $u/c$ bits, the universe for one block is of size $u^{1/c}$.
One table is of size $u^{1/c}$ (we assume the hash value are machine words, as in~\cite{Patrascu:2011:PST:1993636.1993638}),
so the total space used is $O(cu^{1/c})$.
The time spent is $O(c)$, since each lookup is $O(1)$.
Simple tabulation hashing is 3-independent, but not 4-independent.


\section{Chaining}
Because of the birthday paradox, hashing collisions in the table are very probable\footnote{unless we know all keys up front, and $n\leq m$}.
Therefore we need a scheme to handle collisions, the simplest of which is \emph{chaining}.
Each buchet in the hash table is a linked list of the values mapping to that bucket.

What can we say about the length of the chain?
Let $C_t$ be the length of chain $t$.
$\E[C_t] = \sum\limits_i \Pr[h(x_i) = t]$
If we have universal hashing we know that $\Pr[h(x_i) = t] = O(1/m)$,
so $\E[C_t] = O(1)$, for $m = \Omega(n)$

Since we need to traverse the list for all operations, the cost is quadratic in $C_t$,
so we are interested in $\E[C_t^2]$:
\[\E[C_t^2] = 1/m \sum_{s \in [m]} E[C_s^2] = 1/m \sum_{i \neq j} \Pr[h(x_i) = h(x_j)]\]
If we have universal hashing this is $\frac{1}{m} n^2 O(\frac{1}{m}) = O(n^2/m^2) = O(1)$ for $m = \Omega(n)$.
With a totally random hash function $C_t = O(\frac{\log n}{\log\log n})$ with probability $1 - 1/n^c$ for any $c$.
This also holds for simple tabulation hashing.


\section{Perfect Hashing (FKS hashing)}

Idea: resolve collisions with another layer of hash tables.

On collision in bucket tables, rebuild the table using a different hash function.
When $n$ gets too large, double $m$ and start over, in order to keep the number of elements in the bucket tables small.
If a bucket table is too large, double its size and rehash.

Since $\E[C_t]$ is the number of elements that should not collide in the table, we can adjust the table size in such a way that
$\E[C_t] \leq 1/2$, so $\Pr[\text{no collisions in } C_t] \geq 1/2$.
Use size $\Theta(C_t^2)$ for the bucket tables.
This makes the expected number of rebuilds of the bucket tables $O(1)$ before getting zero collisions.

$\E[\text{space}] = \Theta(m + \sum\limits_t C_t^2) = \Theta(m + n^2/m) = \Theta(n)$ for $m=\Theta(n)$.

Results: $O(1)$ deterministic query, $O(n)$ expected update (w.h.p.), $O(n)$ space.


\section{Linear Probing}

Idea: store values directly in the table. On collision, look for next available spot.
On deletion, replace element with a ``tombstone'', so that searches does not stop too early.
Great for cache performance.
The main problem of linear probing is the increasing lengths of the ``runs'',
that is intervals of non-empty cells.

We require $m \geq (1+\epsilon) n$ (not just $m=\Omega(n)$), in order to have available cells in the table.
Space is naturally $O(m)$.
With a totally random hashing function, or by using tabulation hashing, the expected time for operations is $O(1/\epsilon^2)$
With a $O(\log n)$-wise or 5-wise independent hashing function, constant time is expected.


\section{Cuckoo Hashing}
Idea: have two hash tables with different hashing functions.
On collision, swap the colliding values, and try to insert the swapped value in the other table.
Deletes are simple.
If we get a cycle (swap $a$ with $b$, swap $b$ with $c$, and $c$ hashes to $a$ again), we rebuild the tables.
The table sizes are $m \geq (1+\epsilon)n$, so the space used is $O((2+\epsilon)n)$.

Any value $x$ is either in $A[h_A(x)]$ or $B[h_B(x)] \implies O(1)$ deterministic query.
If the hashing functions are fully random or $\log n$-wise independent we get $O(1)$ expected update and $O(1/n)$ probability of failure.



\chapter{Static Tree Queries}%
\label{ch:statictrees}

\topics{Range Minimum Query (\code{RMQ}{i, j}), Lowest Common Ancestor (\code{LCA}{x, y}), Level Ancestor (\code{LA}{x, n}), Range Queries, Range Trees.}

We would like $O(1)$ query time on selected operations, and still only $O(n)$ space;
if we allow $O(n^2)$ space this is trivial, as we can simply precompute all queries and store them.

\section{Range Minimum Query}
We would like to retrieve the index of the minimum element in an array, between index $i$ and $j$.
Our goal is to get $O(n)$ time and space preprocessing, and constant time query.
Note that this is easy to do in $O(\log n)$ time using Range Trees ---
store minimum in internal nodes, and traverse from $i$ to $j$ in $O(\log n)$ time.

It turns out that \LCA{} and \RMQ{} are equivalent.

\subsection{Reduction from \RMQ{} to \LCA{}}

\todo{Add tree from lecture notes}
Build a \emph{Cartesian Tree\label{sec:cartesian-tree}}:
Walk through the array, while keeping track of the right spine of the tree.
When inserting a new element, if the element is the largest element in the spine, insert it at the end.
Else, we have an edge from $v$ to $w$, where the new element $a$ should be in between.
Make $a$ the right child of $v$, and make $w$ the \emph{left} child of $a$.
This step looks like it will be linear, but
the more we have to search through the right spine, the more swaps we do,
and the smaller the spine gets, so it amortizes to constant time,
making the algorithm linear.

Note that simpler divide and conquer algorithm runs in $O(n \log n)$.

We see that \code{LCA}{i, j} in the cartesian tree is the same as \code{RMQ}{i, j} in $A$.

\subsection{Reduction from \LCA{} to \RMQ{}}

Traverse the tree in-order, and write out the \emph{depth} of each node to $A$.
Now \code{RMQ}{i, j} = \code{LCA}{i, j}.
Naturally, since this scheme should work for any tree, we cannot write out the node values, since
the tree may not be a cartesian tree.

Note that if we go from \RMQ{} to \LCA{} and back again, we end up with different numbers
in the array. However, since we are not interested in the actual minimum, but only the index of the minimum,
the two arrays act exactly the same.
A consequence of this is that we get \emph{Universe reduction}, where we have mapped the universe $\mathcal{U}$ to $[n-1]$.

\section{Constant time \LCA{} (\RMQ{})}%
\label{sec:constant-lca}

\subsubsection{Step 1: Reduction}
We start by reducting the problem to $\pm 1 \textsc{RMQ}$, in which adjacent elements of the array differs by at most 1.
Walk an \emph{Euler Tour} of the tree:
\todo{Add figure}
visit every edge twice, and for each edge write down the node we left.
Each node store a pointer to the first visit of that node in the array, and the array elements store a pointer to its element in the tree.
\RMQ{} and \LCA{} are still equivalent.

We need this later on (step 4).

\subsubsection{Step 2: Precomputation}
Get $O(1)$ time and $O(n \log n)$ space \RMQ{}.
Precompute and store all queries from any starting point where the interval length is a power of 2.
Since there are $n$ starting points, and $\log n$ powers of 2 to choose from, there are $n \log n$ such queries.
The key observation is that any arbitrary interval is the union of two such intervals.
For instance $A[4..11] = A[4..8] \cup A[7..11]$.
The double counting does not matter, since $\min$ is an idempotent operation.
The intervals are trivially computed.

\subsubsection{Step 3: Indirection}
Indirection.
Make a two layer structure: divide the numbers in $A$ into groups of size $1/2 \log n$, which makes the bottom layer.
The top layer consists of the minimum element in each block. Since there are $n/(2 \log n) = 2n/\log n$ such blocks,
there are equally many items in the top layer.

A query in this structure consists of (potentially) three parts:
A query in the bottom block in which $i$ is,
a query in the top block for all blocks which are completely covered by the interval $[i, j]$,
and a query in the bottom block in which $j$ is.
We need all three queries to be $O(1)$.

The gain from this is that the top layer only stores $O(n/ \log n)$, so we can afford Step 2, since the $\log$ factors cancel.
We get $O(1)$ query and $O(n)$ space for the top structure.

\subsubsection{Step 4: Lookup Tables}
We use lookup tables for the bottom groups.
The groups are of size $n' = 1/2 \log n$.
\RMQ{} queries in these groups are invariant over value ``shifts'' in the gruop:
if we add $a$ to all elements in the group, the queries are still the same.
Shift all groups by its first element, such that all groups start with 0.
Now every group is completely defined by the difference of adjacent elements,
so the blocks can be encoded as a bitstring of the same length as a block, where 0 is decreasing and 1 is increasing:
$[3,4,5,4] \rightarrow [0,1,2,1] \rightarrow [-, 1, 1, 0]$.
There are $2^{n'} = \sqrt{n}$ possible such blocks,
${(1/2 \log n)}^2$ possible queries, and each answer requires $\log \log n$ bits,
so storing a lookup tables for all possible blocks, over all possible queries with all possible
answers take $\sqrt{n}\ {(1/2 \log n)}^2\ \log \log n = o(n)$ bits.
Now each bottom block can simply store a pointer into the table, and we get $O(1)$ query for the bottom groups.


\section{Constant Time \LA{}}
Level Anscestor queries take a node $x$ and a level $n$, and the goal is to find the $n$th parent of $x$ in the tree.
The simplest way to do this is for each node to store its parent, making the query $O(n)$.
We want $O(1)$.

\subsubsection{Step 1: Jump Pointers}
Instead of having each node storing only its parent, each node can store its $2^k$th parent.
Each node has $O(\log n)$ such parents, making the space requirement $O(n \log n)$.
Query time is $O(\log n)$, since we at least halve $n$ each jump.

\subsubsection{Step 2: Long-path Decomposition}
Decompose the tree into a set of paths.
Find the longest path in the tree from the root, and store the nodes in an array.
The nodes themselves store the array and its index in the array.
Recurse on the subtrees that are hanging from the path.

With this scheme, a query is done as follows:
if $n$ is less than the nodes index in its path, we jump directly to the node.
Else, we jump to the first node in our path, subtract $n$ by $x$s index, and repeat.
We risk at most to visit $O(\sqrt{n})$ such paths, since we know that the paths are the \emph{longest} paths.
We end up using $O(n)$ space, and $O(\sqrt{n})$ query time.

\subsubsection{Step 3: Ladder Decomposition}
Extend each path upwards by twice its length.
Now the arrays overlap, but the nodes still only store their original array and index.
This doubles the space of Step 2, but we are still linear.
The improvement of this step is that we at least double the length from the node to the end of its path,
since the path in which we can jump freely goes at least twice that length up.

\subsubsection{Step 4: Step 1 + Step 3}
We combine the jump pointers and the ladder decomposition.
Jump pointers are great for long jumps, and ladders are great for short jumps.
We follow the jump pointer $k/2 \leq 2^{\floor{\log k}} \leq k$ steps up, for some $k$.
Since we have gone up a path from $x$ to a node by the jump pointer, we know that the node we hit is
of large height, and hence is part of a long ladder. Since its height from the end of the path
can be doubled by Step 3, we can get from $k/2$ to $k$, in which we know our target is.
Hence, we get $O(1)$ query, but still $O(n \log n)$ space (and preprocessing).

\subsubsection{Step 5: Only Leaves Store Jump Pointers}
Since all nodes have constant access to a leaf node (by its ladder, of which the last node is a leaf, by the maximal property),
only leaves need to store the jump pointers.
In other words, we make all queries start at leaves.

\subsubsection{Step 6: Leaf Trimming}%
\label{sec:first-leaf-trim}
\begin{definition}{Maximally Deep Node}
    A node with $\geq \frac{1}{4} \log n$ descendants.
\end{definition}

Split the tree in two layers by the maximally deep nodes.
The number of leaves in the top part is now $O(n/\log n)$, since
\todo{eh?}
for each $1/4 \log n$ nodes in the original tree we have ``replaced'' it with a subtree (the bottom structure).
If we now use Step 5 on the top, we get $O(n)$ space.

\subsubsection{Step 7: Lookup Table}
For the bottom trees, we use lookup tables.
The trees are of size $n' \leq 1/4 \log n$. The number of rooted trees on $n'$ nodes is limited by
$2^{2n'} \leq \sqrt{n}$ by encoding an euler tour as a string of $\pm1$, like in Section~\ref{sec:constant-lca}.
There are ${(n')}^2 = O(\log^2 n)$ possible queries (if $n$ is large, we just go to the top structure),
and an answer takes $O(\log \log n)$ bits,
so a lookup table for all possible trees, with all possible queries takes only
$\sqrt{n}\ O(\log^2 n)\ O(\log \log n) = o(n)$ bits.

We end up with $O(1)$ time queries, using $O(n)$ space!



\chapter{Strings}

\topics{String search, suffix trees, suffix arrays.}

We want to to \emph{String Matching} efficient: given a \emph{text} $T$ and a \emph{pattern} $P$
we want to see if $P \in T$, or to find all occurences of $P$ in $T$.
Both $P$ and $T$ are strings over some alphabet $\Sigma$.
There exists linear time algorithms to do this, like \algo{Knuth-Morris-Pratt},
\algo{Boyer-Moore}, or \algo{Karp-Rabin}.

We look at a static data structure on $T$, with the goal of getting string matching in $O(|P|)$ time and $O(|T|)$ space.

\section{Warmup: Library Search}
Given a set of strings $T_1, \dots, T_k$, we query with a pattern $P$ and want to get $P$s predecessor among the $T$s.

\begin{definition}{Trie}
    A Trie sis a rooted tree with child branches labeled with letters in $\Sigma$.
Let $T$ be the number of nodes in the trie. This is bounded by $\sum^k_{i=1} T_i$ (equality if no pair of strings share a prefix).
\end{definition}
\todo{Add figure}

A trie can encode multiple strings, by having the edges in a path from the root to a leaf spell out the string.
However, we need a terminal symbol $\$$ to denote the end of a string, so we can have prefixes of a string in the same trie\todo{Bad expl?}.
If each node traverses its edges in sorted order an in-order traversal of the trie yields the strings of the trie in sorted order.

\subsection{Trie Representation}
How do we represent a trie?
More specifically, how does each node represent its children?

\subsubsection{Array}
Nodes can store an array of length $\Sigma$, with pointers to the next nodes, or $\bot$ pointers signaling absence.
Query for a node in $O(1)$ time, predecessor can also be $O(1)$ by having each node point to its predecessor, since the tree is static.
The real downside of this approach is the space, since it is proportional to the alphabet size.

\subsubsection{Balanced Binary Search Tree}
We can put nodes in a BBST for each child, with a pointer to the child node.
Each query is $O(\log\Sigma)$, and there are $O(T)$ queries to be done.
Predecessor is simple, and space is $O(T)$.

\subsubsection{Hash Table}
We can use a hash table to map characters from $\Sigma$ to a pointer to the child node.
This is fast, so query is $O(P)$ in total. However, we do not support predecessor queries, which we need.
Space is $O(T)$.

\subsubsection{van Emde Boas/y-fast tree}
Use a van Emde Boas tree for the children, which allows lookup in $O(\log\log\Sigma)$ time.
Also handles predecessor.
See Section~\ref{sec:vEB} for details on the van Emde Boas tree.

\subsubsection{Hashing + vEB}
Have both a hash table \emph{and} a van Emde Boas tree.
Use the hash table until we get a miss, and use the tree to find its predecessor.
After this first miss, we only care about the largest string in the remaining subtree,
which can be explicitly stored for the hash tables, since it is only a constant overhead per node.
This makes the query time $O(P + \log\log\Sigma)$, since we only use the tree once.

\subsubsection{Weight Balanced BST}
Instead of having a balanced BST over each nodes children, we can weight each child with the number of leaves in its subtree.
This ensures that every second jump in the BST either reduces the number of candidate strings \emph{in the trie} to $2/3$ of its size,
or it finds a new trie node in the WBBST (hence we advance $P$ one letter).
An intuition for this claim is this\todo{Add array figure}:
we might be so lucky as to cut out $1/2$ of the leaves when leaving a node, unless there is some really heavy child in the middle
(remember we have to retain ordering).
But then in the next step this large child will surely be either to the far left or to the far right, which means we either follow it
(which gets us to a new node in the trie), or we discard it, discarding a large number of leaves.

We end up with a running time of $O(P + \log k)$ where $k$ is the number of leaves, and remain at $O(T)$ space.

\subsubsection{Leaf Trimming}
\begin{definition}{Maximally Deep Node}
    A node with $\geq \Sigma$ leaf descendants.
\end{definition}

As in Section~\ref{sec:first-leaf-trim} we cut the tree in two parts, the top part and the bottom parts.
The tree is cut at the minimal maximally deep nodes.
Now the number of leaves in the top part is $\leq |T| / |\Sigma|$,
and the number of branching nodes in the top part is \emph{also} $\leq |T| / |\Sigma|$.
Now we can use arrays in the top part of the tree as well as for the cut nodes, since
there are only $|T| / |\Sigma|$ nodes, so the $\Sigma$s cancel for the space.
For the non-branching nodes, nodes that only have one descendant, we can simply store its decendant and its label.
For the bottom part of the tree we can use leaf trimming, since $k=\Sigma$, by the definition of maximally deep nodes.

We end up using $O(T)$ space for the top structure, and get $O(P + \log\Sigma)$ query time.

Table~\ref{tab:trie-node-repr} sums up all approaches, with query time and space requirement.

\begin{table}[h]
    \centering
    \begin{tabular}{l l l l}
        & Node representation & Query & Space\\\midrule
       1& Array & $O(P)$ & $O(T\Sigma)$ \\
       2& Balances BST & $O(P \log \Sigma)$ & $O(T)$ \\
       3& Hash Table & $O(P)$ & $O(T)$ \\
       3.5& van Emde Boas/y-fast tree & $O(P\log\log\Sigma)$ & $O(T)$ \\
        3.75& (3) + (3.5) & $O(P + \log\log\Sigma)$ & $O(T)$ \\
        4 & Weight-balanced BST & $O(P + \log k)$ & $O(T)$\\
        5 & Leaf Trimming + (1) + (4) & $O(P + \log\Sigma)$ & $O(T)$
    \end{tabular}
    \caption{Table over node representation, query time, and space requirement.}%
\label{tab:trie-node-repr}
\end{table}

\section{Suffix Tree}
\begin{definition}{Compressed Trie}
    A trie where all internal nodes are branch nodes, and the edge labels are strings over $\Sigma$ rather than characters.
\end{definition}

A Suffix Tree is a compressed trie of all suffixes of a string.
The tree has $|T| + 1$ leaves: one leaf for each suffix, including the empty string.
The edge labels are typically stored as indices in the string, instead of the string itself.
Instead of appending $\$$ to each of the suffixes, which are the strings we are inserting into the tree,
we can simply append $\$$ to the string $T$, since this will make it the last character in all of the suffixes.
The structure takes $O(T)$ space.
\todo{add figure}

\subsection{Applications of Suffix Trees}
Suffix trees are surprisingly useful, and with some of the results from Chapter~\ref{ch:statictrees}
we can get some impressive results.

\subsubsection{String Matching}
A search for $P$ in the tree yields a node which leaves corresponds to all matches of $P$ in the text.
The search is done in $O(P)$ time (trivial).
We can then list the first $k$ occurences of $P$ in $O(k)$ time, by simply traversing the subtree.
If we precompute the number of leaves below all nodes, we can retrieve the number of occurences of a string in
$O(1)$ time after the inital search, making the total time $O(P)$.

\subsubsection{Longest Repeating Substring}
We are looking for the longest substring $S \subseteq T$ that is present at least twice.
This can be done in $O(T)$ time using suffix trees, since it is the branching node of maximum ``letter depth''.

\subsubsection{Longest Substring Match for $i$, $j$}
How long is the longest common substring for $T[i..]$ and $T[j..]$?
Find the two nodes \LCA{} in $O(1)$ time to get the common prefix.

\subsubsection{Something more}
\todo{here}

\subsubsection{TODO this}
\todo{here}

\section{Suffix Arrays}
While suffix trees are constructable in $O(T)$ time, it is difficult.
We look at a simpler structure, the Suffix Array, which is equivalent to a suffix tree, but easier, although slower, to construct.

\begin{definition}{Suffix Array}
    An array $A$ of indices into a text $T$ such that $a_i$ gives the suffixes $T[a_i:]$ in sorted order.
\end{definition}

We let $\forall_{\sigma\in\Sigma}\ \$ < \sigma$.
Suffix arrays are searchable in $O(P \log T)$ time using binary search.
In addition to the suffixes, the suffix array also holds information about the difference in adjacent suffixes:
This allows for faster searching, as we know how much of the adjacent suffix matches what we already have matched.

\begin{definition}{\algo{LCP[$i$]}}
    Longest common prefix of $i$th and $i+1$th suffix in the order they are in the suffix array.
\end{definition}

\begin{example}
    Consider $T=\texttt{banana\$}$. The suffixes are shown in Table~\ref{tab:suffixes}, and the suffix array is shown in Table~\ref{tab:suffix-array}.
    Note that the suffixes are not stored explicitly in the array, but only the indices $i$ and the \algo{LCP}.

    \begin{figure}[h]
        \centering
        \begin{subfigure}{0.45\textwidth}
            \centering
            \begin{tabular}{l l}
                $i$ & Suffix\\\midrule
                0 & \texttt{banana\$}\\
                1 & \texttt{anana\$}\\
                2 & \texttt{nana\$}\\
                3 & \texttt{ana\$}\\
                4 & \texttt{na\$}\\
                5 & \texttt{a\$}\\
                6 & \texttt{\$}
            \end{tabular}
            \caption{The suffixes of $T$%
\label{tab:suffixes}}
        \end{subfigure}
        \begin{subfigure}{0.45\textwidth}
            \centering
            \begin{tabular}{l l l}
                $i$ & Suffix              & \algo{LCP}\\\midrule
                6 & \texttt{\$}         & 0 \\
                5 & \texttt{a\$}        & 1 \\
                3 & \texttt{ana\$}      & 3 \\
                1 & \texttt{anana\$}    & 0 \\
                0 & \texttt{banana\$}   & 0 \\
                4 & \texttt{na\$}       & 2 \\
                2 & \texttt{nana\$}     & $-$
            \end{tabular}
            \caption{The Suffix Array of $T$.%
\label{tab:suffix-array}
            }
        \end{subfigure}
    \end{figure}
\end{example}

\subsection{Suffix Tree $\rightarrow$ Suffix Array}
This way is simple: traverse the tree in-order.

\subsection{Suffix Array $\rightarrow$ Suffix Tree}
We make a Cartesian Tree (see Section~\ref{sec:cartesian-tree}) of the \algo{LCP} array.
This time we put \emph{all} minimum values at the root\footnote{note that the number of 0s in the array is equal to the number of different characters in $T$}.
The suffixes of $T$ are the leaves of the tree.
Note that the \algo{LCP} value of the internal nodes is the letter depth of that node,
\todo{Add figure}
so the edge length between two internal nodes is the difference in \algo{LCP}.
We know from Section~\ref{sec:cartesian-tree} that this is doable in linear time.

\subsection{Construction}
If we have the suffix array it is possible to construct the \algo{LCP} array in linear time\todo{ref}.
We look at a method of constructing the suffix array from scratch in $O(T + \text{sort}(\Sigma))$ time.

\begin{definition}{$\big<a, b\big>$}
    Let $\big<a, b\big>$ denote the concatenation of the strings $a$ and $b$.
\end{definition}

\subsubsection{Step 1}
Sort $\Sigma$. This step can be skipped if we do not need the children of the suffix tree nodes in order.
If we skip this step, the construction is done in $O(T)$ time.

\subsubsection{Step 2}
Replace each letter in the text by its rank in the sorted array.
By doing this we guarantee that $|\Sigma'| \leq |T|$, in case $|\Sigma|$ is really large.

\subsubsection{Step 3}
Let
\begin{align*}
    T_0 &= \big<(T[3i+0], T[3i+1], T[3i+2]) \text{\ for\ } i=0,1,2,\dots\big>\\
    T_1 &= \big<(T[3i+1], T[3i+2], T[3i+3]) \text{\ for\ } i=0,1,2,\dots\big>\\
    T_2 &= \big<(T[3i+2], T[3i+3], T[3i+4]) \text{\ for\ } i=0,1,2,\dots\big>
\end{align*}
If $T=\texttt{banana}$,
$T_0 = \big<\texttt{ban}\ \texttt{ana}\big>$,
$T_1 = \big<\texttt{ana}\ \texttt{na}\big>$, and
$T_2 = \big<\texttt{nan}\ \texttt{a}\big>$.
We think of the elements of $T_i$ as ``letters''.
Our goal is to use the $T$s to construct the suffix array for $T$.
Note that $\textsc{Suffix}(T) \cong \textsc{Suffix}(T_0) \cup \textsc{Suffix}(T_1) \cup \textsc{Suffix}(T_2)$.

If $T=\texttt{banana}$,
$\textsc{Suffix}(T_0) = \{\texttt{ban\ ana},\ \texttt{ana},\ \epsilon\}$, since we operate on the triplets as letters.

\subsubsection{Step 4}
Recurse on $\big<T_0, T_1\big>$. End up with a suffix array of the suffixes in $\big<T_0, T_1\big>$.
Note that the number of suffixes when recursing is $O(2/3)$ of what we started with.

\subsubsection{Step 5}
Now we want to use the suffix array just obtained to radix sort the suffixes in $T_2$.
Note that \[T_2[i..] = T[3i+2..] = \big<T[3i+2],\ T[3i+3..]\big> = \big<T[3i+2],\ T_0[i+1..]\big>.\]
We can take off the first letter of the suffix, and get a suffix which we know the sorted order or, since it is in $T_0$, which we sorted in Step 4.
This is like Radix sort, but with only two values, both of which can be compared in $O(1)$.
This allows us to sort $T_2$.

\subsubsection{Step 6}
Merge $T_2$ into $T_0, T_1$.
While this seems straight forward (merging is $O(n)$) we still need to make sure that the suffix comparisons are done in constant time.
This is done in a similar fashion to Step 5: take off the first letter in each suffix and rewrite the suffix in terms of
a single letter + suffixes we already know the order of.

Since all operations are linear, with the exception of the recursive call, we get the following recurrence:
$T(n) = T(\frac{2}{3} n) + O(n) = O(n)$.
Linear time!

\chapter{Temporal Structures}

\topics{Partial persistency, full persistency, funcitonal persistency, pareial retroactivity, full retroactivity.}

When working with temporal data structures, our machine model is the \emph{Pointer Machine}

\begin{definition}{Pointer Machine}
    A computational model in which we have \emph{Nodes} with $O(1)$ fields.
    The fields can be values or \emph{Pointers}, which points to other nodes.
    Field access, node creation, data operations are all $O(1)$ time.
    The pointer machine does not have arrays.
\end{definition}


\section{Persistence}
A persistent data structure is a data strucure that ``never changes''.
On a mutable operation to the structure, a new structure is made.
This means that all operations done to the data strucure is relative to a specific version of the structure.

There are four levels of persistence:
\begin{enumerate}
    \item Partial persistence: Only the latest version is editable. The versions are linearly ordered through time.
    \item Full persistence: Any version can be updated, to produce a new version. The versions makes a tree.
    \item Confluent persistence: Versions can be merged to produce a new version. The graph is now a DAG\@.
    \item Functional: Nodes in the data structur are never modified, only new ones are created. The version of the structure is maintained by a pointer.
\end{enumerate}


\subsection{Partial Persistence}
Any data structure using the pointer machine with $\leq p = O(1)$ pointers to any node in any version can be made partially persistent,
with $O(1)$ amortized multiplicative overhead and $O(1)$ space per change.
We show how this can be done.

Each node store \emph{Back Pointers}, which points to all nodes that have a pointer to this node.
Since there are at most $p$ such pointers, this is $O(1)$ extra space.
In addition, the nodes store a history of modifications $(version, field, value)$ tuples.
The history is of size $\leq 2p$ (using the fact that $p=O(1)$).
On field reads we read the value explicitly stored in the node, and then apply all the modifications that were done up to the verison
we are reading from.
When the history is full, we create a new node with the entire modification history applied to its fields, and an empty history.
Now we need to update the back pointers of the nodes we point to, since these nodes also store back pointers.
This is easy, since the back pointers are not persistent.
But we also need to update the pointers (not back pointers) of other nodes (which is the nodes we have in our back pointer list),
and these pointers are persistent, so we must recurse.

It is not trivial to see that this recursion terminates.
What if the nodes we update get a full history from updating their pointer to us,
which makes us update our pointers making our history full again?

We can use the \emph{Potential Method} for amortized analysis.
Remember that \emph{Amortized cost} is actual cost + change in potential.
Let $\Phi = c \cdot \Sigma$, where $\Sigma$ is the number of modifications in all nodes latest versions.
Observe that when we make a change, the amortized cost is
\[\leq c + c\ [- 2cp + p \cdot \text{recursions}]\text{?}\]
The first $c$ is for computation, the second $c$ is the added potential, since we
just added one modification to a node,
and $[-2cp + p \cdot \text{recursions}]\text{?}$ are for the recursions, if there is one.
If there is no recursion, we have constant time.
If there is a recursion, we replace it by the same expression, which causes the $-2cp$ to cancel.
We do end up with another recursion, but if it does happen, we still get rid of the $-2cp$ term.

In conclusion, we use $O(3p) = O(1)$ extra space for each node, and allow $O(1)$ extra time on updates, to
get partial persistence for any data structure.


\subsection{Full Persistence}
We take a similar approach to full persistency as we did with partial persistency.
The first difference is that we need \emph{all} pointers to be bi-directional, and not only the field pointers, as previously.
The second and most important difference is that now versions of the structure is no longer a line, but a tree.
In order to go around this problem we linearize the version tree:
traverse the tree, and write out first and last visit of each node\todo{add figure}.

However, we need this structure to be dynamic,
so we use an \emph{Order Maintenance data structure},
which supports insertion before or after a given item in $O(1)$ (like a linked list),
and supports relative order query of two items in $O(1)$ time.

Let $p$ still be the in-degree of nodes.
Let $d$ be the maximum number of fields in a node.
We now allow $2(d + p + 1)$ modifications in a nodes history.

A single nodes history now consists of the same triples, but the $version$ can no longer be compared by $\leq$,
since the versions are in a tree. This is what we need the $O(1)$ relative ordering for.

On field read we can simply go through all modifications in the node (since there is a constant of them),
and use relative ordering to find the latest update of the field we are reading, from an ancestor of the current version.

Updates when the history is full is different from the approach taken in partial persistence.
We would like to split the history tree into two parts of the same size,
and apply all of the modifications from the root to the newly cut out subtree to the new node.
This was the original node loses the modifications in the new subtree, and the new node loses
the modifications that are left in the original node.
Now we need to update pointers.
We have $d$ fields, $p$ back pointers, and $d + p + 1$ items in the history, all of which could be pointers,
which makes $\leq 2d + 2p + 1$ pointers.
Amortization scheme still works out (although the potential function is slightly different), and we get $O(1)$ updates.

\subsubsection{}
Confluent persistency and functional were not covered in class.


\section{Temporal Data Structures}

Temporal data structures allow all operations to specify a time in which the operation is to be performed.
The key difference between temporal and persistent structures is that in a temporal structure previous alterations to the structure
should ``propagate'' through time, and update the current structure.
A persistent data structure would not update the current strucure, but simply make a new data structure for each of the paths taken through time.

\subsection{Retroactivity}
We need three operations:
\begin{enumerate}
    \item \code{Insert}{t, $\ op(\dots)$}: retroactively perform the specified operation at time $t$.
    \item \code{Delete}{t}: retroactively undo the operation at time $t$.
    \item \code{Query}{t, $\ op(\dots)$}: execute the query at time $t$.
\end{enumerate}

We differentiate between \emph{Partial retroactivity}, in which we are only allowed to \algo{Query} in the present,
and \emph{Full retroactivity}, in which we may query whenever we want.

\subsubsection{A Simple Case}
If the updates we perform are commutative ($x, y = y, x$) and invertible ($x, x^{-1} = \varnothing$)
then partial retroactivity is easy:
Insert operations can be done in the present, since the ordering does not matter, and
delete operations can be done as inverse insert operations.

An example is if we were to sum a sequence of numbers.
If we sum $1 + 3$ and would like to insert a $+2$ in between, we can put it at the end.
If we want to delete the $+3$, we can add a $-3$ at the end.

\subsection{Full Retroactivity}
What do we need for full retroactivity?

\begin{definition}{Decomposable Search Problem}%
\label{sec:dsp}
    $\text{query}(x, A\cup B) = f(\text{query}(x, A), \text{query}(x, B))$
\end{definition}

\begin{example}
    \algo{Nearest-Neighbour}, \algo{Successor}, and \algo{Point-Location} are all decomposable search problems.
\end{example}

If what we query is a DSP, we can achieve full retroactivity in $O(\log m)$ factor overhead,
where $m$ is the number of retroactive operations.
We can do this by using a \emph{Segment Tree} over the operations.
We think of the operations as begin in a time interval, from they are made until they are deleted.
Then we can store the operations in the nodes of the maximal subtrees that covers the interval.
Each node in the segment tree has its own copy of the underlying datastructure which we are making retroactive.
Since there are $O(\log m)$ nodes an element can be in, and the individual results can be joined \emph{somehow} (via $f$, since the problem is a DSP),
we get $O(\log m)$  multiplicative overhead.


\subsection{General Transformations}
What can we do if we do in general?
The most obvious method is the \emph{Rollback Method}:
when we want to do a retroactive change, we roll back the data structure to the given time,
make the change, and replay all changes afterwards.
This makes for a $O(r)$ multiplicative overhead, where $r$ is the number of time units in the past.
Unfortunately, depending on the exact model used, this is the best we can do in general.

There is a lower bound: $\Omega(r)$ overhead can be necessary for retroactivity.
This means that the most efficient way to make retroactive changes is to go back, make the change,
and redo whatever comes after --- the rollback method!

To see why this is the case, consider a very simply computer with two registers $X$ and $Y$, and with the following operations:
$X=x$, $Y\mathrel{+}=\Delta$, and $Y = XY$.
On query, the machine returns $Y$, and all operations are $O(1)$.
The operation sequence
\[\big<Y \mathrel{+}= a_n,\ Y=XY,\ Y\mathrel{+}= a_{n-1},\ \dots,\ Y\mathrel{+}= a_0\big>\]
computes the polynomial $\sum^{n}_{i} a_{i}x^{i}$.
We can use this to compute the polynomial for any $X$ by retroactively inserting $X=x$ at $t=0$.
However, it is not possible to reeveluate such a polynomial using field operations any faster than to just evaluate it again.


\subsection{Priority Queue}
We now look at an example of a retroactive priority queue that supports
\algo{Insert}, \algo{Delete-Min}, and is partially retroactive.
We assume keys are only inserted once.

We can plot the lifetime of the queue in 2D, where the x dimension is time and the y dimensions in key value.
\todo{add plot}
Keys in the queue are plotted as points when they are inserted, and are extended as horizonal rays.
On \algo{Delete-Min}, we shoot a ray from the x-axis at the time of the delete upward untill it hits a horizontal ray.
This makes $\rceil$ patterns.

Let $Q_{t}$ be the set of keys in the queue at time $t$.
What happens if we \code{Insert}{t, \text{insert}$(k)$}?
Its ray will extend to the right and hit a deletion ray, which will delete it.
This will make the element that ray previously deleted to not be deleted after all,
so its ray will extend further to the right and hit another deletion ray.
In effect, the element that ends ut not getting deleted is
$\max\{k, k' \mid k' \text{\ deleted at time} \geq t\}$, but this relation is hard to maintain.

In order to make things easier we define a \emph{Brige}.

\begin{definition}{Bridge}
    A Bridge is a time $t$ such that $Q_t \in Q_{\text{now}}$
\end{definition}

Now if $t'$ is the bridge preceding $t$ we see that
\[\max\{k'\mid k' \text{\ deleted at time}\geq t\} = \max\{k'\notin Q_{\text{now}} \mid k' \text{\ inserted at time}\geq t'\}\]
In other terms, the largest key deleted after a time $t$ is the largest key inserted after the previous bridge that is not in the final set.

Now we can store $Q_{\text{now}}$ as a BBST on values, and all insertions in a BBST on time.
The latter trees nodes is also augmented with the value of the largest insert in its subtree that is not in $Q_{\text{now}}$.
At last, we store a third BBST with \emph{all} the updates, ordered on time, and also augmented as follows:
\[\text{Augmentation} =
\begin{cases}
    0 \text{\ if \code{insert}{k}, and\ }k \in Q_\text{now}\\
    +1 \text{\ if \code{insert}{k}, and\ }k \notin Q_\text{now}\\
    -1 \text{\ if \algo{Delete-Min}}\\
\end{cases}\]
In addition the internal nodes store subtree sums and min/max prefix sums.
We do this in order to detect brdiges, since a bridge is a prefix summing to 0.
When we have to find out which element to insert into $Q_{\text{now}}$ we can walk up from the node in the insertion BST,
and find the max to the right, since this BST stores this for all subtrees.
$O(\log n)$ time.


\subsection{Other Structures}
We list other strucutes that can be made retroactive.
A Queue can be made partial retroactive with $O(1)$ overhead and full retroactive with $O(\log m)$ overhead.
A Deque and \algo{Union-Find} can also be make fully retroactive with $O(\log m)$ overhead.
The priority queue, which we just made partially retroactive with $O(\log m)$ overhead,
can be made fully retroactive with $O(\sqrt{m} \log m)$ overhead.
Successor queries can be done in $O(\log m)$ partial retroactive,
and since it is a decomposable search problem (see~\ref{sec:dsp}) we can pay a $\log$ factor to make it fully retroactive,
with $O(\log^2 m)$ overhead. However, it is also possible to get full retroactivity with only $O(\log m)$ overhead.


\section{List Order Maintenance}
Before tackeling the real problem, we look at an easier problem.

\subsection{List Labeling}
We want to store integer labels in a list, such that insert/delete here queries are constant,
and that the list is in a strictly monotone ordering.
\emph{Label Space} is the size of the labels as a function of the number of elements in the list we want to store.
Table~\ref{tab:list-labeling} shows the best known updates for different sizes of the label space.

\begin{table}[b]
    \centering
    \begin{tabular}{c l}
        Label Space & Best known update\\\midrule
        $(1+\epsilon)n\dots n \log n$ & $O(\log^2 n)$ \\
        $n^{1 + \epsilon} \dots n^{O(1)}$ & $O(\log n)$ \\
        $2^n$ & $O(1)$
    \end{tabular}
    \caption{%
\label{tab:list-labeling}%
        Table showing label space vs best known update for \algo{List-Labeling}}
\end{table}





\chapter{Geometry}

\chapter{Connectivity in Dynamic Graphs}

Dynamic connectivity on trees, euler tour trees.


\chapter{Lower Bounds}

Dynamic partial sums, dynamic connectivity.


\chapter{Integer Structures}

van Emde Boas, x-fast trees, y-fast trees, fusion trees.

\section{van Emde Boas Tree}%
\label{sec:vEB}

\chapter{Succinct Structures}
Rank, Select

\chapter{Concurrency}

Locks, Lock-free structures, lists, priority queues.

\printbibliography%

\end{document}

