structures.tex

\chapter{Advanced Data Structures}

In the previous chapter, we showed how three different bit string encodings of ordinal trees can be turned into data structures which support wide varieties of operations, provided that they are equipped with the \rank{} and \select{} (and later \match{} and \enclose{}) indices.
Here we present data structures which are fundamentally different in either the primitive operations they use, or that they require more advanced encoding instead of being based on a single bit string.

\begin{description}
	\item[Fully-Functional (FF)] 
	A data structure built on top of the BP representation which replaces the set of traditional indices by new more general index.
	This results in a structure which supports not only all operations which BP did -- the old primitive operations are special cases of the new ones, but also allows to implement those operations which either required a specialized index, or they simply were not possible.
	
	\item[Tree Covering (TC)]
	Tree covering is a data structure based on a recursive decomposition of the tree into mini-trees and micro-trees which are then encoded.
	Each level of the decomposition is stored and processed in a different way.
	Since it is tree structure rather than bit string oriented, it is easier to augment it with small pieces of information which are required by various operations.
	This is a big difference from
	\begin{enuminline}
		\item discovering, more than inventing, the inner rules of the representations, which we did with ranking and selecting;
		\item or developing general indices which cover the bit string in various blocks on multiple levels.
	\end{enuminline}
	
	\item[Universal Succinct Representation (USR)]
	An attempt to develop a universal data structure which diminishes the differences between several representations.
	It provides a view to the BP and DFUDS bit string representation as well as decomposition into micro-trees.
	Its main advantage is that it automatically benefits from any indices which are proposed for either BP, DFUDS, or TC representations.
\end{description}

%\todo{Mention transformation into a binary tree}

\section{Fully Functional Representation}

The BP representation which we described in the previous chapter was based on using \rank{} and \select{}, and \match{} and \enclose{} operations as the main tool.
There were several operations which required an additional index (\childAny{} and \levelAncestor{}), and several operations which were not supported at all (\levelAny{}).
All the operations which we have just listed have one thing in common: they can all be expressed using more general operations.
We did not show the indices for \levelAncestor{} in the BP and DFUDS representations for a reason: they were unnecessarily complicated, whereas here in the Fully Functional data structure, it is going to be one of the easiest operations.

The data structure was developed by \cite{sadakane2010fully}.
The name Fully Functional refers to the set of operations, that the structure offers full range of functionality.

We define a new set of primitive operations for which we then design a single index, incorporating even the range operation.
The index will be general -- any of the representations (LOUDS, BP, DFUDS) can use it, however only BP will benefit from it.

\subsection{New Operations}

We follow on the section \ref{ss:rmq-def} and define more operations on the bit string $S$ parametrized by the function $g$ which is to be applied.
\begin{description}
	\item[The sum operation]
	Since \rank{} will no longer be a primitive operation, we cannot use it to compute $G[i]$.
	It is therefore replaced by an operation \summ{} which is equivalent to $G[j] - G[i - 1]$, which we used before in \ref{ss:rmq-def}.
	It is defined as:
	$$ \summ(S, g, i, j) = \sum_{k=i}^j g(S[k]). $$
	
	\item[Linear search operations]
	We replace \select{} in all forms by linear searching operations.
	\begin{description}
		\item[\fwdSearch{}]
		Returns the first position $j$ after a given position $i$ such that the values sum up to $d$:
		$$ \fwdSearch(S, g, i, d) = \min_{j > i} \{j : \summ(S, g, i, j) = d\}. $$
		
		\item[\bwdSearch{}]
		Works the same way as \fwdSearch{} except that it searches towards the beginning of the bit string:
		$$ \bwdSearch(S, g, i, d) = \max_{j < i} \{j : \summ(S, g, j, i) = d\}. $$
	\end{description}
	
	Note that despite having used the same names in section \ref{s:match-enclose}, their definition here is different.
	They refer to operations defined for all $i \in [0, N)$, rather than only to look-up tables. 
	
	\item[Range operations]
	We generalize the range operations for any function $g$.
	We also extend the original operation \rmqi{} into \rmqSelect{}, so that it does not only return the first occurrence of the minimum, but any occurrence in general.
	
	\begin{description}
		\item[\rmq{}]
		Returns the value of the minimum in the given range.
		$$\rmq(S, g, i, j) = \summ(S, g, 0, i - 1) + \min_{i \le k \le j} \summ(S, g, i, k)$$

		\item[\rmqSize{}]
		Returns how many occurrences of minimum there are in the given range:
		$$\rmqSize(S, g, i, j) = | \{i \le k \le j : \summ(S, g, 0, k) = \rmq(S, g, i, j) \} |. $$
		
		\item[\rmqRank{}]
		Returns how many occurrences of minimum there are in the given range up to position $r$.
		This can be directly implemented using \rmq{} and \rmqSize{}:
		\begin{algorithm}
		\begin{algorithmic}
		\Function{\rmqRank}{$S, g, i, j, r$}
			\If{$\rmq(S, g, i, j) \ne \rmq(S, g, i, r)$}
				\State \Return{$0$}
			\Else
				\State \Return{$\rmqSize(S, g, i, r)$}
			\EndIf
		\EndFunction
		\end{algorithmic}
		\end{algorithm}
		
		\item[\rmqSelect{}]
		Returns the position $p$ of the $r$-th minimum in the range $i, j$:
		$$\rmqSelect(S, g, i, j, r) = \min_{p \ge i} \{p : \rmqRank(S, g, i, j, p) \ge r\}.$$
		
		\item[\RMQ{}, \RMQSize{}, \RMQRank{}, \RMQSelect{}]
		The maximum variants of the range operations are defined similarly.
	\end{description}
\end{description}

\bigbreak

We show how it is possible to realize all operations which we used as primitives in the previous succinct data structures only by sums, searches and range operations on calculated arrays.
We immediately get a data structure equivalent to those in the previous chapter in terms of the operations which they support.
Later we will show that even more operations become feasible for the FF representation.

We recall the definitions of the functions $\phi, \psi, \pi$ from the section \ref{ss:rmq-def}:
\begin{align*}
	\phi(b) &= b, \\
	\psi(b) &= 1 - b, \\
	\pi(b) &= 2 b - 1.
\end{align*}

\begin{description}
	\item[Operations on general bit strings]~\vspace{-1\baselineskip}
	\begin{align*}
		\rank_1(i) &= \summ(S, \phi, 0, i) \\
		\select_1(n) &= \fwdSearch(S, \phi, 0, n) \\
		\rank_0(i) &= \summ(S, \psi, 0, i) \\
		\select_0(n) &= \fwdSearch(S, \psi, 0, n)
	\end{align*}
	
	\item[Operations on balanced bit strings]~\vspace{-1\baselineskip}
	\begin{align*}
		\findClose(i) &= \fwdSearch(S, \pi, i, 0) \\
		\findOpen(i) &= \bwdSearch(S, \pi, i, 0) \\
		\enclose(i) &= \bwdSearch(S, \pi, i, 2) \\
		\enclose(i_1, i_2)&\ \textrm{stays the same} \\
		\rmqi(E, i, j) &= \rmqSelect(S, \pi, i, j, 1) \\
		\RMQi(E, i, j) &= \RMQSelect(S, \pi, i, j, 1)
	\end{align*}
\end{description}

Therefore, while designing the index, we can focus only on the new operations.

\subsection{The Succinct Index}

As we are describing a universal index which is independent of its specific usage for representing trees, we again use $N$ to denote the size of the bit string.
We also parametrize all operations by the function $g$ which will be fixed for the rest of this section.

The structure of the index follows the general idea of dividing into blocks and them into small blocks.
Here the blocks will be of roughly polylogarithmic size and small blocks of size $b = \frac{\log N}{2}$ in order to be processed by using look-up tables.
If the query spans multiple small blocks within a single block, the queries are handled by min-max trees.
The queries spanning multiple blocks are answered by a macro structure.

\bigbreak

The small blocks are small enough to by used as indices of precomputed look-up tables, which answer all queries in constant time.
We use the following look-up tables which directly implement the primitive operations on small blocks:
\begin{description}
	\item[\summ{}]
	For a given range $i, j$, it returns the sum $v$.
	
	\item[\fwdSearch{}, \bwdSearch{}]
	For a given position $i$ and value $d$, they return the first next and previous position $p$ where the difference is $d$.
	If the answer is not present, a special value is returned.
	
	\item[\rmq{}, \RMQ{}]
	For a given range $i, j$, they return the local value $v$ of minimum and maximum.
	
	\item[\rmqSize{}, \RMQSize{}]
	For a given range $i, j$, they return the number $r$ of occurrences of them minimum and maximum.
	
	\item[\rmqSelect{}, \RMQSelect{}]
	For a given range $i, j$ and $r$, they return the position $p$ of $r$-th minimum and maximum in the small block.	
\end{description}

The values of $i, j, r$ are in range $[0, b - 1]$; the values $d, v$ are in range $[-b, b]$; the value of $p$ is in range $[0, b - 1]$ plus the special value indicating that such position does not exist in the small block.
Together we have 9 precomputed tables; each of them requires $O(\sqrt{N} \log N \log \log N)$ bits of memory.

The tables are used to answer all range operations whenever $i$ and $j$ are in the same small block.
In case of the searches, they also determine that the answer is not present in the small block.

We also use the look-up tables to handle the prefix and suffix of a range query, or at the beginning or the end of a search query.

\subsection{Min-Max Tree}

Each block contains $k^c$ small blocks for $k = \frac{\log N}{\log \log N}$ and an arbitrary integer constant $c \ge 1$.
The value of the constant $c$ will be discussed at the end.
The purpose of the min-max tree is to lift the operations from $b$ bits to $b k^c$ while retaining their constant running time.

The $l$-th block covers an interval of $B = b k^c$ bits spanning from the position $l B$ to $(l + 1) B - 1$.
To simplify the description we isolate the block by shifting the offsets so that it covers the range $[0, B - 1]$ by setting $l = 0$.
We also assume that the values in the array $G$ are in range $[-B, B]$; the global values can be computed simply by adding the value $G[l B - 1]$.
This does not have any impact on the correctness of the operations on the block level.

We extend the bit string $S$ to the nearest multiple of $B$ in order to ensure that each block is full.
The extra space caused by the extension is negligible.
Only the \fwdSearch{} operation could return an answer from the extended part, however it can happen only if the answer was not found earlier -- this case is easy to handle in the end.

\bigbreak

We build a perfect $k$-ary tree on top of the sequence of the small blocks (belonging to the block); we call it the \emph{min-max tree}.
The tree has a constant height equal to $c$.
Its leaves represent the information from the small blocks provided by the look-up tables; the inner nodes aggregate the information from their children.
We store the following values in each node which spans over the range $i, j$:
\begin{description}
	\item[$e = \summ(S, g, 0, j)$] 
	The value at the end of the range.
	
	\item[$m = \rmq(S, g, i, j), \ms = \rmqSize(S, g, i, j)$]
	The minimum value and how many times it occurs.
	
	\item[$M = \RMQ(S, g, i, j), \Ms = \RMQSize(S, g, i, j)$]
	The maximum value and how many times it occurs.
\end{description}

The aggregation in the inner node is the obvious one:
\begin{iteminline}
	\item the last value for $e$;
	\item minimum for $m$, maximum for $M$;
	\item sum for $\ms$ and $\Ms$.
\end{iteminline}
All values within a node require only $O(\log b)$ bits each.

As it is a perfect $k$-ary tree, we store the values of the nodes in a heap-like fashion in arrays $e[\cdot], m[\cdot], \ms[\cdot], M[\cdot], \Ms[\cdot]$.
We can navigate in this tree from an node with number $n$ to the parent ($\lfloor n / k \rfloor$), first child ($n \cdot k$), last child ($n \cdot k + k - 1$), previous sibling $n - 1$, next sibling $n + 1$.

All children of a node are stored together in consecutive $O(k \log \log N) = O(\log N) = c' b$ bits of memory, for a constant $c'$.
There are $\frac{k^{c + 1}}{k - 1} = O(k^c)$ nodes, each of them requires $O(\log b)$ bits.
The density of the tree structure built on top of the sequence of the small blocks is $O\left(\frac{k^c \log b}{k^c b}\right) = O\left(\frac{\log b}{b}\right) = o(1)$.

\bigskip

We show how to support the operations on the block level using traversal of the min-max tree and possibly delegation to small blocks.
By $b(i)$ we denote the index of the small block which contains the position $i$.
Contrary to the defined numbering of nodes, in order to simplify the notation, we assume in the algorithms that the node numbers of leaves are the same as indices of the small blocks with which they are associated.
We will use subscripts to refer to bits of $S$ represented by a small block $n$: $S_n = S[n b : (n + 1) b]$

\begin{algorithm}
\begin{algorithmic}
\Function{\sumBlock}{$S, g, i, j$}
	\State $x \gets e[b(i - 1) - 1] + \summ[S_{b(i - 1)}, g, 0, (i - 1) \% b]$
	\State $y \gets e[b(j) - 1] + \summ[S_{b(j)}, g, 0, j \% b]$
	\State \Return{$y - x$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Search Operations}

We say that the small block $j$ \emph{covers} a value $v$ if $m[j] \le v \le M[j]$.

\begin{lemma}\label{l:search}
	The answer to a search query starting at $i$ and looking for a difference $d$ (such that it is not answered in the small block $b(i)$) is in the first small block $j$ such that covers $v = \summ(S, g, 0, i) + d$.
	
	No small block in the subtree of a min-max tree node not covering the value $v$ contains the answer.
\end{lemma}
\begin{proof}
	Let us recall an important property of the $\pm 1$ functions $g$: 
	$$| G[i] - G[i-1] | \le 1.$$
	From that it follows that each small block contains all values between its minimum and maximum.
	The first small block which covers the desired value $v$ has to contain it.
	
	Moreover, if $v < \rmq[S_{b(i)}, (i + 1) \% b, b - 1]$ (less than minimum of the rest of the small block), then it is sufficient to find the first small block $j$ such that $m[j] \ge v$ because $M[j] \ge m[j-1]$.
	A similar statement holds for $v$ being greater than the maximum.
	
	The extremes of a leaf are the same as of the small block with which it is associated.
	If a small block $j$ contains the answer, then the value $v$ is covered by the leaf $j$.
	Because of the aggregation method of inner vertices, all ancestors of $j$ cover $v$ too.
	An inner vertex covers $v$ only if a leaf in its subtree covers $v$.
\end{proof}

When we process the search operations, we first check the small block containing $i$ for an answer.
If the answer is present there, we return the position, and stop.

Otherwise, we compute the desired value $v$ and traverse the tree up until we find the answer or until we reach the root.
If we get to root, we signal that this block does not contain the answer by returning a special value.
When we are in a node $a$, we check the extremes of its siblings in the direction in which we are searching.
This check can be performed in time $c'$ using a precomputed look-up table as all siblings are stored in consecutive $c' b$ bits.
Only one-sided checks are necessary as we noted in the lemma \ref{l:search}.

When we find a sibling covering $v$, we move to it and start descending to its first child covering the value $v$.
Finding such child again requires time $c'$ and another set of precomputed tables.
Once we descend to a leaf $j$, we compute the value $d' = v - e[j - 1]$ which we are going to look for in the associated small block using a look-up table. 
As the height of the tree is $c$, the whole operation takes at most $O(2 c c') = O(1)$ steps.

We show the pseudocode for the operation \fwdSearch{}.
By an asterisk superscript we denote a repeated application of a look-up table on the list of consecutive nodes in the tree.

\begin{algorithm}
\begin{algorithmic}
\Function{\fwdSearchBlock}{$S, g, i, d$}
	\State $p \gets \fwdSearch[S_{b(i)}, g, i \% b, d]$
	\If{$p \ne -1$}
		\State \Return{$p + b(i) b$}
	\Else
		\State $v \gets e[b(i) - 1] + \summ[S_{b(i)}, g, 0, i \% b] + d$
		\State $n \gets b(i)$ \Comment{The current node, initialized to be a leaf}
		\While{$(j \gets \nodeSearch^*[\rightSiblings(n), v]) = -1$} \Comment{Sibling search}
			\State $n \gets \parent(n)$
			\If{$\isRoot(n)$}
				\State \Return{$-1$}
			\EndIf
		\EndWhile
		\While{$\boolnot \isLeaf(j)$}
			\State{$j \gets \nodeSearch^*[\children(j), v]$} \Comment{The first child covering $v$}
		\EndWhile
		\State $d' \gets v - e[j - 1]$ \Comment{The remaining difference}
		\State \Return{$j b + \fwdSearch'(S_j, g, 0, d')$} \Comment{$d'$ in the small block $j$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

Note that the final \fwdSearch' is the standard \fwdSearch{} altered to allow the answer $0$, which is prohibited by the original definition.
This can be handled with a simple check for $\summ[S_j, g, 0, 0] = d'$.

\subsubsection{Range Operations}

The range operations work similarly: they traverse the tree up gathering information on the way, and in case of range select operations, they descend down.
If the query is fully contained within a small block, the answer is found in a look-up table.
In order to solve the other queries, we use two helper functions.
By the same argument as for the search operations, the running time is $O(2 c c') = O(1)$.

The helper function \rmqInfo{} which returns aggregated information for all siblings of a given node.
The function returns a tuple containing: the number of the first node, the number of the last node, the minimum, the maximum, the number of occurrences of the minimum, the number of occurrences of the maximum.
It iterates over $\frac{k}{c'}$ nodes in each step using look-up tables, which results in the running time $O(c')$.

Another helper function \rmqList{} gathers all aggregated info for subranges between $i$ and $j$.
It starts with the leaves $u = b(i)$ and $v = b(j)$, and keeps two lists of partial answers, one for each starting point.
We first ask the small blocks for their answers and remember them in their respective lists.

In a loop until $u$ and $v$ merge, we get the answers from the right siblings of $u$ and the left siblings of $v$, we remember them in the lists and move to their parents.
In the last iteration the left siblings and the right siblings overlap; therefore we store the answers in only one of the lists.
Each list contains at most $c$ values as the table look-ups aggregate the answers.
We combine the lists into a single list and find the answer to the queries in it.

\begin{algorithm}
\begin{algorithmic}
\Function{\rmqList}{$S, g, i, j$} \Comment{$b(i) \ne b(j)$}
	\State $L \gets [\,]$%
	\Instr $R \gets [\,]$ \Comment{Initialization of the empty lists}
	\State $i_m \gets \rmq[S_{b(i)}, g, i \% b, b - 1] + e[b(i) - 1]$ \Comment{Similarly $j_m, i_M, j_M$}
	\State $i_{\ms} \gets \rmqSize[S_{b(i)}, g, i \% b, b - 1]$ \Comment{Similarly $j_{\ms}, i_{\Ms}, j_{\Ms}$}
	\State $\append(L, \{\struct{f}{b(i)}, \struct{l}{b(i)}, \struct{m}{i_m}, \struct{\ms}{i_{\ms}}, \struct{M}{i_M}, \struct{\Ms}{i_{\Ms}} \})$ \Comment{Info for $b(i)$}
	\State $\prepend(R, \{\struct{f}{b(j)}, \struct{l}{b(j)}, \struct{m}{j_m}, \struct{\ms}{j_{\ms}}, \struct{M}{j_M}, \struct{\Ms}{j_{\Ms}} \})$ \Comment{Info for $b(j)$}
	\While{$\parent(u) \ne \parent(v)$} \Comment{$u, v$ in different subtrees}
		\State $\append(L, \rmqInfo(S, g, u, \str{r}))$
		\State $\prepend(R, \rmqInfo(S, g, v, \str{l}))$
	\EndWhile
	\State $\append(L, \rmqInfo(S, g, u, v))$ \Comment{Between $u$ and $v$}
	\State $\concatenate(L, R)$
	\State \Return{$L$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\bigbreak

For \rmq{} we return the minimum of the list obtained from \rmqList{}.

\begin{algorithm}
\begin{algorithmic}
\Function{\rmqBlock}{$S, g, i, j$}
	\If{$b(i) = b(j)$}
		\State \Return{$\rmq[S_{b(i)}, g, i \% b, j \% b] + e[b(i) - 1]$}
	\Else
		\State $L \gets \rmqList(S, g, i, j)$
		\State $m \gets \infty$
		\ForAll{$I \gets L$}
			\State $m \gets \min(m, I.m)$
		\EndFor
		\State \Return{$m$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

For \rmqSizeBlock{} we sum $\ms$ for those info-nodes whose minimum is equal to the global one calculated by \rmq{}.

\begin{algorithm}
\begin{algorithmic}
\Function{\rmqSizeBlock}{$S, g, i, j$}
	\If{$b(i) = b(j)$}
		\State \Return{$\rmqSize[S_{b(i)}, g, i \% b, j \% b]$}
	\Else
		\State $m \gets \rmqBlock(G, i, j)$
		\State $L \gets \rmqList(G, i, j)$
		\State $ms \gets 0$
		\ForAll{$I \gets L$}
			\If{$I.m = m$}
				\State $\ms \gets \ms + I.\ms$
			\EndIf
		\EndFor
		\State \Return{$\ms$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

In case of \rmqSelect{}, we find the first node $n$ in the list such that the prefix sum of $\ms$ is greater than or equal to $r$.
We descend in such node into the first child whose left siblings including itself sum up to $r$, and repeat until we get to a leaf.
Once we are in a leaf, we use a look-up table to solve the select there.

\begin{algorithm}
\begin{algorithmic}
\Function{\rmqSelectBlock}{$S, g, i, j, r$} \Comment{Assuming $r$-th min exists}
	\If{$b(i) = b(j)$}
		\State $p \gets \rmqSelect[S_{b(i)}, g, i \% b, j \% b, r]$
		\State \Return{$b(i) b + p$}
	\Else
		\State $m \gets \rmqBlock(G, i, j)$
		\State $L \gets \rmqList(G, i, j)$
		\State $ms \gets 0$
		\ForAll{$I \gets L$}
			\If{$I.m = m$}
				\If{$\ms + I.\ms \ge r$}
					\State \Break
				\EndIf
				\State $\ms \gets \ms + I.\ms$
			\EndIf
		\EndFor
\algstore{rmqselect}
\end{algorithmic}
\end{algorithm}

When the loop is broken, $I$ contains the information about list of siblings node with one of them containing the desired minimum.
Using look-up tables which are similar to \nodeSearch{}, we descend into the right child.
The table also returns the new remaining number of occurrences by subtracting those in nodes before $p$.

We first search the restricted range of nodes provided by $I$, keeping track of the number of the occurrences which we are interested in.

\begin{algorithm}
\begin{algorithmic}
\algrestore{rmqselect}
		\State $(p, r) \gets \minSearch^*[\nodeRange(I.f, I.l), r - I.ms]$
		\While{$\boolnot \isLeaf(p)$}
			\State $(p, r) \gets \minSearch^*[\children(p), r]$
		\EndWhile
		\State $x \gets \max(i, p b) \% b$%
		\Instr $y \gets \min(j, (p + 1) b - 1) \% b$
		\State \Return{$b(p)b + \rmqSelect[S_{p}, g, x, y]$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

There are seven look-up tables necessary for traversal and processing the tree.
The tables have an additional (not mentioned) parameter which restricts the size of the block to be processed.
Whenever an index of a node is returned, it is turned into a node number by adding the number of the leftmost node involved in the query.
\begin{description}
	\item[\fwdSearch]
	The table is looking for the node which contains the first occurrence of $v$ in the block of consecutive nodes.
	\bwdSearch{} requires another table returning the position of the last occurrence $v$.
	
	\item[\rmqInfo]
	Four tables aggregating information for consecutive nodes are necessary; the tables compute minimum, maximum, and sum conditioned by the value of minimum or maximum of the other nodes in the given range.
	
	\item[\rmqSelect]
	One table which is looking for the $r$-th occurrence of the minimum.
	It returns the index of the node and the number of occurrences of the minimum in its preceding siblings.
	\RMQSelect{} requires a similar table for occurrences of the maximum.
\end{description}
All tables are defined for blocks of $b$ bits with $O(1)$ parameters of size $O(\log k^c) = O(\log \log N)$.

\subsection{Macro Structure}

The macro structure starts with five arrays which summarize the results from the underlying blocks (the root nodes of their min-max trees).
\begin{description}
	\item[$e[i\char93$]
	The value at the end of the block $i$; in comparison to the block level, here we store the absolute values (the same for minima and maxima).
	Each element has size of $O(\log N)$ bits.
	
	\item[$m[i\char93$, $M[i\char93$]
	The minimum and maximum values of the block $i$.
	
	\item[$ms[i\char93$, $Ms[i\char93$]
	The number of their occurrences in the block $i$.
	Each element is of size $O(\log \log N)$ bits.
\end{description}

\bigbreak

We denote $B(i)$ to the index of the block containing the position $i$.

The algorithm for \summ is very similar to \sumBlock.

\begin{algorithm}
\begin{algorithmic}
\Function{\summ}{$S, g, i, j$}
	\State $x \gets e[B(i - 1) - 1] + \sumBlock(S_{B(i - 1)}, g, 0, (i - 1) \% B)$
	\State $y \gets e[B(j) - 1] + \sumBlock(S_{B(j)}, g, 0, j \% B)$
	\State \Return{$y - x$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Search Operations}\label{ff-search}

For each block $i$ we define an array of \emph{left-to-right minima} $\lrm_i$ such that
\begin{align*}
	\lrm_i[0] &= i \\
	\lrm_i[j + 1] &= \min \{k : k > \lrm_i[j] \booland m[k] > m[\lrm_i[k]]\}
\end{align*}
Similarly we define left-to-right maxima arrays $\LRM_i$, and for backward searching we define the arrays $\rlm_i$ and $\RLM_i$.
We focus only on left-to-right direction.

The arrays $\lrm$ and $\LRM$ can be used to implement the global operation $\fwdSearch(S, g, i, d)$.
Let's assume that the result is not in block $B(i)$, if it was, we can solve it on the block level.
We are looking for a block $j \ge B(i) + 1 = n$ such that $j$ covers the value $v = \summ(S, g, 0, i) + d$.
There are three possibilities of how to find the block $j$:
\begin{enumerate}
	\item If $n$ covers $v$, then the first block after $B(i)$ contains the answer.
	\item If $v < m[n]$, we search for the block in the array $\lrm$.
	\item Otherwise, we search in the array $\LRM$.
\end{enumerate}
It can happen that the value $v$ is not covered by any block $j$, in which case we report a failure.

\begin{algorithm}
\begin{algorithmic}
\Function{\fwdSearch}{$S, g, i, d$}
	\State $p \gets \fwdSearchBlock(S_{B(i)}, g, i \% B, d)$ \Comment{Block operation offset}
	\If{$p \ne -1$}
		\State \Return{$B(i) B + p$}
	\Else
		\State $v \gets \summ(S, g, 0, i) + d$
		\State $n \gets B(i) + 1$
		\If{$v < m[n]$}
			\State $j \gets \lrmSearch(n, v)$
		\ElsIf{$v > M[j]$}
			\State $j \gets \LRMSearch(n, v)$
		\Else
			\State $j \gets n$
		\EndIf
		\If{$j = -1$} \Comment{A search reported that $v$ is not covered.}
			\State \Return{$-1$}
		\Else
			\State $d' \gets v - \summ(S, g, 0, B(j) B - 1)$
			\State \Return{$B(j) B  + \fwdSearchBlock'(S_{B(j)}, g, 0, d')$}
		\EndIf
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

Note that the final call of \fwdSearchBlock{}' is the standard block operation \fwdSearchBlock{} altered to allow the answer $0$.
The same was necessary for the search on the block level.

\bigbreak

It remains to show a constant time algorithm for the operation \lrmSearch{} (\LRMSearch{} is similar).
The \naive{} approach would be to store each $\lrm_i$ as an array $A$ turned into a compressed array using operation \succ{}.
The array $A$ is defined partially for all $j$ in $\lrm_i$: $ A[M[i] - m[j]] = j$.
The problem with this approach is that, the compressed arrays for all $i$ can contain $O\left(\left(\frac{N}{B}\right)^2\right)$ runs in total, which is too much.

\bigbreak

We observe that the arrays $\lrm_i$ are alike.
\begin{lemma}
	Let a block $a$ be in two different arrays $\lrm_i$ and $\lrm_j$: 
	$$ \lrm_i[x_i] = a = \lrm_j[x_j], $$
	then all following values in the arrays are the same:
	$$ \lrm_i[x_i + k] = \lrm_j[x_j + k] \ \forall k \ge 0. $$
\end{lemma}
\begin{proof}
	It follows from the definition of the array $\lrm$
\end{proof}

\label{Tlrm} We define a tree $T_{\lrm}$ which is built as a trie for reversed $\lrm$ arrays.
We add an artificial root, in order to make it a tree; it will not be used in algorithms.

\begin{example}
	Let $m = [6, 4, 9, 7, 4, 4, 1, 8, 5]$, then the arrays $\lrm_i$ are:
	\begin{align*}
		\lrm_0 &= [0, 1, 6] &
		\lrm_1 &= [1, 6] &
		\lrm_2 &= [2, 3, 4, 6] \\
		\lrm_3 &= [3, 4, 6] &
		\lrm_4 &= [4, 6] &
		\lrm_5 &= [5, 6] \\
		\lrm_6 &= [6] &
		\lrm_7 &= [7, 8] &
		\lrm_8 &= [8]
	\end{align*}
	The tree $T_{\lrm}$ built from the arrays is shown in the figure \ref{fig:ex:tlrm}.
	The values of $m$ are in parentheses.
	
	\begin{figure}
		\centering
		\begin{tikzpicture}
		[
			every node/.style = {
				shape=rectangle, rounded corners,
				draw, align=center
			},
			baseline,
			align=center,
			level distance=2\baselineskip,
			text depth=.1em,
			text height=.8em,
			level 1/.style={sibling distance=10em},
			level 2/.style={sibling distance=5em},
			level 3/.style={sibling distance=2em},
			level 4/.style={sibling distance=1em}
		]
		\node {root}
			child { node {6 (1)} 
				child { node {1 (4)}
					child { node {0 (6)} }
				}
				child { node {4 (4)}
					child { node {3 (7)}
						child { node {2 (9)} }
					}
				}
				child { node {5 (4)} }
			}
			child { node {8 (5)}
				child { node {7 (8)} }
			};
		\end{tikzpicture}
		\caption{An example of tree $T_{\lrm}$ (\cite{sadakane2010fully}).}
		\label{fig:ex:tlrm}
	\end{figure}
\end{example}

The properties of the tree are:
\begin{enumerate}
	\item $m[\parent(i)] < m[i] \le m[\parent(i)] + B$;
	\item $i < \parent(i)$;
	\item the tree has $\frac{N}{B} + 1$ nodes.
\end{enumerate}

The search for the value $v$ in $\lrm_i$ is transformed to a search for an ancestor $j$ of $i$ in the tree $T_{\lrm}$ such that $m[j] \le v$.
We split the search into two parts:
\begin{enumerate}
	\item a search in $\lrm_i$ restricted to powers of two;
	\item a search in $\lrm_i$ with a bounded distance.
\end{enumerate}

\bigbreak

We use the $\langle O(n \log n); O(1) \rangle$ algorithm for querying level ancestor introduced in \cite{bender2004level}.
Instead of searching through the whole array $\lrm_i$, we limit the number of elements to $\log N$:
$$ \lrm'_i[j] = \lrm_i[2^j]. $$
This array is turned into a tiny compressed array of jumps $J_i$ requiring only $O(\log^2 N)$ bits of space, which is $O\left(\frac{N}{B} \log^2 N\right) = o(N)$ for $c \ge 2$.

By using the tiny compressed array, we move from node $i$ to a node $j'$ of $T_{\lrm}$ for which we bounds on depth and height, and the number of ancestors which we have to search through.
\begin{align*}
	\dep(j') - \dep(j) &< \dep(i) - \dep(j') \\
	\hei(j') &\ge \dep(i) - \dep(j') \\
	\dep(j') - \dep(j) &< \hei(j')
\end{align*}

Note that if we tried to be more clever and represent nodes $j$ which cover values $m[i] - m[j]$ instead of those at distance $2^j$, then the bounds would not hold.

\bigbreak

The tree gets decomposed iteratively to paths; in each step the longest path $p$ from a node $\start(p)$ to a leaf $\en(p)$ is removed.
If the path contains $l = \length(p)$ nodes, we prepend it with $l$ more ancestors (or less if the root is reached) and call it a \emph{ladder}.
There are as many ladders as leaves of the tree $T_{\lrm}$, and all ladders together contain $\le 2 \frac{N}{B}$ nodes.
Note that the root of the tree $T_{\lrm}$ is not represented in the ladders.

The previous bound guaranties that the final answer $j$ is in the ladder which was extended from a path containing the node $j'$, to which we got by using the tiny compressed dictionary $J_i$.
We represent each ladder by an array of block indices (which are nodes of $T_{\lrm}$) covering the value $M[\start(p)] - v$ (using maximum makes sure that the whole block $\start(p)$ is represented).
We combine all ladders together in a single compressed array $L$ which leads to $2 \frac{N}{B}$ runs in total; as the difference of $m[i] - m[\parent(i)] \le B$ is bounded, the total number of elements is $O(N)$.
The space complexity of the compressed array $L$ is $O\left(\frac{N}{B} \log N\right) + o(N) = o(N)$

For each block $i$, we also store the index $l$ of the ladder, which is also the index of the part in the compressed dictionary $L$, in an array $\ladder$.
The size of the array is $O\left(\frac{N}{B} \log N\right) = o(N)$ bits.

\begin{algorithm}
\begin{algorithmic}
\Function{\lrmSearch}{$i, v$}
	\State $j' \gets J_i[M[i] - v]$ \Comment{Jump by power of two}
	\State $l \gets \ladder[j']$ \Comment{The ladder containing $j'$}
	\State $\en \gets L[l, 0]$
	\State $j \gets L[l, M[\en] - v]$ \Comment{If the index is out of the range, $-1$ is returned}
	\State \Return{$j$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Range Operations}

We split the queried range into a prefix, suffix, and span.
The solution for the prefix and suffix is solved on the block level; we focus on supporting the operations for spans of the queries.

We use a helper function \rmqiSpan{} which was defined in lemma \ref{lemma:rmq2} with two minor differences:
\begin{enumerate}
	\item it is defined directly for the array $m[\cdot]$ instead of $E$ and $P$;
	\item it returns indices of the first and the last block containing the minimum;
	\item contrary to \rmqi{} shown in \ref{sss:rmq-index}, it is sufficient to use only one level provided that we set $c \ge 2$.
\end{enumerate}

\begin{algorithm}
\begin{algorithmic}
\Function{\rmq}{$S, g, i, j$}
	\State $m_1 \gets e[B(i) - 1] + \rmqBlock(S_{B(i)}, g, \prefix(i, j))$
	\State $m_2 \gets e[B(j) - 1] + \rmqBlock(S_{B(j)}, g, \suffix(i, j))$
	\State $(f, l) \gets \rmqiSpan(m, \spann(i, j))$
	\State $m_3 \gets m[f]$
	\State \Return{$\min(m_1, m_2, m_3)$}
\EndFunction
\end{algorithmic}
\end{algorithm}

The structure for \rmqiSpan{} cannot be extended for querying the number of occurrences of the minimum nor selecting the $r$-th one.
If we augmented each precomputed interval of size $2^k$ with the number of occurrences, we would still fit in the same space.
The problem stems for the inability of an easily combination of information from the two intervals, like the $\min$ function does.
In this case, the inclusion-exclusion principle would have to be used: adding the numbers of occurrences in both intervals and subtracting the number of occurrences in the overlapping part.
Since the size of the overlapping part is not a power of two in general, and so its number of occurrences is not precomputed, it leads to recursion and running time $O(\log N)$.

\subsubsection{Structures for \rmqSize{} and \rmqSelect{}}

We store the several indexable and fully indexable dictionaries which use the properties of the minima of the blocks.
The idea is to reorder the blocks, which are represented by elements in $m[\cdot]$, so that all blocks containing the same minimum are stored consecutively. 

There are at most $\frac{N}{B}$ distinct minima in range $[-N, N]$.
We store the minima in an indexable dictionary $\mr{}$ offsetted by $N$ to become a range $[0, 2 N]$
The indexable dictionary uses $O\left(\frac{N}{B} \log B\right)$ bits and it supports \rank{} on the minima in constant time.
This is used for referring to $k$-th smallest minimum in the following structures.
We omit the correction of an off-by-one error caused by \rank{} as the smallest minimum has $k = 1$ instead of desired $k = 0$.

For each block minimum $m$ (which is the $k$-th smallest), we define a set containing all blocks which have minimum $m$: $\{ i : m[i] = m\}$.
We represent the set as an indexable dictionary $\mi_k$.
Because of the inequality derived from the generalized Chu-Vandermonde's identity \cite{belbachircombinatorial}, the space complexity of all $\mi_m$ together can be bounded by:
\begin{align*}
	\sum_m S(\mi_k) &= \sum_m \left( \log {\frac{N}{B} \choose |\mi_k|} + o(|\mi_k|) + O(\log \log N) \right) \\
	&\le \log {\left(\frac{N}{B}\right)^2 \choose \frac{N}{B}} + o\left(\frac{N}{B}\right) + O\left(\frac{N}{B} \log \log N\right) \\
	&= O\left(\frac{N}{B} \log N\right) = o(N).
\end{align*}

Finally we define an array $\mpp_k$ for each block minimum $m$ (which is again the $k$-th smallest):
$$\mpp_k\left[\sum_{\substack{j \in \mi_k \\ j \le i}} \ms[j] \right] = i \ \forall i \in \mi_k.$$
We turn all these arrays into a single compressed array $\mpp$ using the operation \succ{}.
The property of this array, from which it was also derived, connects it to a block $t$ which contains the $r$-th occurrence of the $k$-th smallest minimum:
$$ t = \select_1(\mi_k, \mpp[k, r]). $$

All the structures require only $o(N)$ bits of memory.

\bigbreak

As we restricted our queries to their spans, and from \rmqiSpan{} we know the indices of the first and last block containing the minimum, it is easy to find how many occurrences there were before the any block.

\begin{algorithm}
\begin{algorithmic}
\Function{\rmqSize}{$S, g, i, j$}
	\State $\ms_1 \gets 0$%
	\Instr $\ms_2 \gets 0$%
	\Instr $\ms_3 \gets 0$
	\State $m \gets \rmq(S, g, i, j)$
	
	\If{$e[B(i) - 1] + \rmqBlock(S_{B(i)}, g, \prefix(i, j)) = m$} \Comment{In prefix?}
		\State $\ms_1 \gets \rmqSizeBlock(S_{B(i)}, g, \prefix(i, j))$
	\EndIf
	
	\If{$e[B(j) - 1] + \rmqBlock(S_{B(j)}, g, \suffix(i, j)) = m$} \Comment{In suffix?}
		\State $\ms_2 \gets \rmqSizeBlock(S_{B(j)}, g, \suffix(i, j))$
	\EndIf

	\State $(f, l) \gets \rmqiSpan(m, \spann(i, j))$
	\If{$m[f] = m$} \Comment{In span?}
		\State $k \gets \rank_1(\mr, m + N)$ \Comment{$k$-th smallest minimum}
		\State $x \gets \runFirst(\mpp, k, \rank_1(\mi_k, f))$ \Comment{Before the run of $f$}
		\State $y \gets \runFirst(\mpp, k, \rank_1(\mi_k, l))$ \Comment{The block $l$ is not accounted}
		\State $\ms_3 \gets y - x + \ms[l]$
	\EndIf
	\State \Return{$m_1 + m_2 + m_3$}
\EndFunction
\end{algorithmic}
\end{algorithm}

The operation \rmqSelect{} first looks for the minimum in the prefix, then in the span, and finally in the suffix.
The idea of the search in span is to use the property of $\mpp$.

\begin{algorithm}
\begin{algorithmic}
\Function{\rmqSelect}{$S, g, i, j, r$}
	\State $m \gets \rmq(S, g, i, j)$
	\If{$e[B(i) - 1] + \rmqBlock(S_{B(i)}, g, \prefix(i, j)) = m$} \Comment{In prefix?}
		\State $\ms_1 \gets \rmqSizeBlock(S_{B(i)}, g, \prefix(i, j))$ \Comment{Prefix size}
		\If{$\ms_1 \ge r$}
			\State \Return{$B(i) B + \rmqSelectBlock(S_{B(i)}, g, \prefix(i, j), r)$}
		\Else
			\State $r \gets r - \ms_1$
		\EndIf
	\EndIf
	
	\State $(f, l) \gets \rmqiSpan(m, \spann(i, j))$
	\If{$m[f] = m$} \Comment{In span?}
		\State $\ms_3 \gets \rmqSize(S, g, \spann(i, j))$
		\If{$\ms_3 \ge r$}
			\State $k \gets \rank_1(\mr, m + N)$ \Comment{$k$-th smallest minimum}
			\State $x \gets \runFirst(\mpp, k, \rank_1(\mi_k, f))$ \Comment{Before the run of $f$}
			\State $t' \gets \mpp[k, r + x]$
			\State $t \gets \select_1(\mi_k, t')$ \Comment{Block containing the desired occurrence}
			\State $y \gets \runFirst(\mpp, k, t')$ \Comment{Elements before the run of block $t$}
			\State \Return{$t B + \rmqSelectBlock(S_t, g, 0, B - 1, r - y)$}
		\Else
			\State $r \gets r - \ms_3$
		\EndIf
	\EndIf

	\If{$e[B(j) - 1] + \rmqBlock(S_{B(j)}, g, \suffix(i, j)) = m$} \Comment{In suffix?}
		\State $\ms_2 \gets \rmqSizeBlock(S_{B(j)}, g, \suffix(i, j))$ \Comment{Prefix size}
		\If{$\ms_2 \ge r$}
			\State \Return{$B(j) B + \rmqSelectBlock(S_{B(j)}, g, \suffix(i, j), r)$}
		\Else
			\State \Comment{This cannot happen as the bounds of $r$ has been checked}
		\EndIf
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsection{$\pm 1$ Functions Revisited}

We follow in discussion of $\pm 1$ functions which we began in section \ref{ss:rmq-def}.

Although there are 9 functions $g$ mapping $\{0, 1\} \to \{-1, 0, 1\}$, we only use 3 of them in our index: $\pi, \phi, \psi$.
Answers to all operations except for searches with parameters $\phi$ and $\psi$ can be answered using the structure for $\pi$.

For the operation $\summ$, the following identities hold:
\begin{gather*}
	\summ(S, \pi, i, j) = \summ(S, \phi, i, j) - \summ(S, \psi, i, j), \\
	\summ(S, \phi, i, j) + \summ(S, \psi, i, j) = j - i + 1.
\end{gather*}

The explicit formula for \summ{}s follow from the previous equations:
\begin{align*}
	\summ(S, \phi, i, j) &= \frac{(j - i + 1) + \summ(S, \pi, i, j)}{2}, \\
	\summ(S, \psi, i, j) &= \frac{(j - i + 1) - \summ(S, \pi, i, j)}{2}.
\end{align*}

Because the sums of $g \in \{\phi, \psi \}$ are monotonic, we can reduce all range operations to sums and searches.
In the range $i, j$, the minimum occurs for the first time at $i$ and maximum occurs for the last time at $j$.
All occurrences are continuous.
\begin{align*}
	\rmq(S, g, i, j) &= \summ(S, g, 0, i) \\
	\RMQ(S, g, i, j) &= \summ(S, g, 0, j) \\
	\rmqSize(S, g, i, j) &= \min(j + 1, \fwdSearch(S, g, i, 1)) - i \\
	\RMQSize(S, g, i, j) &= j - \max(i - 1, \bwdSearch(S, g, j, 1)) \\
	\rmqSelect(S, g, i, j, r) &= i + r - 1 \\ 
	\RMQSelect(S, g, i, j, r) &= j - \RMQSize(S, g, i, j) + r
\end{align*}

\subsubsection{Search Operations}

The operation \bwdSearch{} can be the reduced to \fwdSearch{} and \summ{}.

\begin{algorithm}
\begin{algorithmic}
\Function{\bwdSearch}{$S, g, i, d$}
	\If{$d > 0$}
		\State $v \gets \summ(S, g, 0, i) - d + 1$
		\If{$v \ge 2 \boolor (v = 1 \booland g(S[0]) \ne 1)$}
			\State \Return{$\fwdSearch(S, g, 0, v)$}
		\ElsIf{$v = 1$}
			\State \Return{$0$}
		\Else
			\State \Return{$-1$}
		\EndIf
	\ElsIf{$d = 0 \booland g(S[i]) = 0 \booland g(S[i-1]) = 0$}
		\State \Return{$i - 1$}
	\Else
		\State \Return{$-1$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

The only non-trivial operation is \fwdSearch{}.
We review the structures which are used in its index and note places which can be simplified.

No simplification is possible for small block (the look-up tables) and block (min-max tree) levels.
In the macro structure, only the tree $T_{\LRM}$ is necessary ($T_{\lrm}$ is not because of the monotonicity of $g$).
The tree is also degenerated into a path.
The tiny compressed array of jumps are not necessary as the whole path forms a ladder; the search in the ladder stays the same.

The operation \fwdSearch{} can be used to implement \select{}, which makes the index for \fwdSearch{} an alternative to the index which we showed in the section \ref{ss:select}.

\begin{algorithm}
\begin{algorithmic}
\Function{\select$_1$}{$S, i$}
	\If{$i \ge 2 \boolor (i = 1 \booland S[0] \ne 1)$} \Comment{In case of \select$_0$: $\ne 0$}
		\State \Return{$\fwdSearch(S, \phi, 0, i)$} \Comment{In case of \select$_0$: $\psi$}
	\ElsIf{$i = 1$}
		\State \Return{$0$}
	\Else
		\State \Return{$-1$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsection{Extension of BP}

The index which we developed in the previous section can be used for any representation, however only the BP representation benefits from it as many operations can be immediately supported.

Child operations, mainly \degree{}, \childRank{}, and \childSelect{}, which are important for basic navigation in the tree, were only available with a specialized index.
They were also the reason for developing the DFUDS representation, which supports them natively.
Using the generalized \rmq{} operations, we present an alternative implementation to the one described by \cite{sadakane2010fully}.
The key observation is that in a representation of a subtree of a vertex $i$ with omitted boundary parentheses, the occurrences of minimum correspond with the terminal parentheses of the children of $i$.

\begin{algorithm}
\begin{algorithmic}
\Function{\degree}{$i$}
	\State \Return{$\rmqSize(S, \pi, i + 1, \findClose(S, i) - 1)$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\Function{\childRank}{$i$}
	\State $p \gets \parent(i)$
	\State \Return{$\rmqRank(S, \pi, p + 1, \findClose(S, p) - 1, \findClose(S, i))$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\Function{\childSelect}{$i, k$}
	\State \Return{$\findOpen(S, \rmqSelect(S, \pi, i + 1, \findClose(i) - 1, k))$}
\EndFunction
\end{algorithmic}
\end{algorithm}

The operation \levelAncestor{} is now a straightforward generalization of \enclose{}.

\begin{algorithm}
\begin{algorithmic}
\Function{\levelAncestor}{$i, d$}
	\If{$d = 0$}
		\State \Return{$i$}
	\Else
		\State \Return{$\bwdSearch(S, \pi, i, d + 1)$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

It is also possible to realize some of the \levelAny{} operations with the restriction to a subtree of a vertex $a$.
The most general ones: \levelSize{}, \levelRank{}, and \levelSelect{} are however not supported.

\begin{algorithm}
\begin{algorithmic}
\Function{\levelFirst}{$a, l$}
	\If{$\dep(S, a) = l$}
		\State \Return{$a$}
	\Else
		\State \Return{$\fwdSearch(S, \pi, a, l - \dep(S, a))$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\Function{\levelLast}{$a, l$}
	\If{$\dep(S, a) = l$}
		\State \Return{$a$}
	\Else
		\State \Return{$\findOpen(S, \bwdSearch(S, \pi, \findClose(S, a), \dep(S, a) - l)$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\Function{\levelNext}{$a, i$}
	\State \Return{$\fwdSearch(S, \pi, \findClose(S, i), 0)$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\Function{\levelPrev}{$a, i$}
	\State \Return{$\findOpen(S, \bwdSearch(S, \pi, i, 0))$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsection{Final Thoughts}

The constant $c$ needs to be set to $c \ge 2$ because of the level-ancestor and range minimum query macro structure.

\bigbreak

The single index which we presented is more general than all the indices which used the BP representation.
As a consequence more operations are supported, in fact more than any of the previous representations.

The only unsupported operations by this index are
\begin{enuminline}
	\item the \rank{} and \select{} in respect to lo-order and dfuds-order numberings of vertices;
	\item arbitrary access for level queries through \levelSize{}, \levelRank{}, and \levelSelect{} operations.
\end{enuminline}

All of the listed operations would benefit from a better handling of the level structure of the tree, an operation like \fwdSearch{} which is parametrized by the number of the occurrence.
If these operations are crucial, the only data structure which supports them is the LOUDS.

\section{Tree Covering}\label{s:TC}

All tree data structures which we have shown so far have one thing in common; they solve their operations on two or three different levels:
\begin{enumerate}
	\item On the lowest level, they are decomposed into small blocks of size $b$ which is less than $\log n$ bits.
	This size makes it possible to precompute results to all possible queries which are contained in a small block.
	
	\item Then on an intermediate level, several small blocks are grouped together to form blocks of size $B = O(\log^c n)$ bits.
	The purpose of this level is to lower the number of blocks for the next level.
	
	\item Finally, the macro level which spans the whole structure connects individual blocks.
	It usually uses data structures which are inspired by the traditional ones which are allowed to use $O\left(\frac{n}{B} \log^{c'} n\right)$ bits where $c' < c$.
\end{enumerate}

So far, the small blocks and blocks were chunks of a bit string representation of the tree.
They did not have any connection to the structure of the tree; all operations were implemented in their most generality for an arbitrary (balanced) bit string.
The representation of a single vertex, let alone the sequence of its children or the whole subtree, could have been covered by multiple (small) blocks.

The tree covering approach respects the structure of the tree by its decomposition into components of bounded sizes.
Not dissimilar to the other representations, it also uses three levels of scale with look-up tables being utilized on the lowest one.

\bigbreak

The basic operations (\childAny{}, \degree{}, \dep{}, \subtreeSize{}, \preAny{}, \postAny{}) were described by \cite{geary2006succinct}.
They were also the first ones who supported the operation \levelAncestor{}.

The more advanced operations (\hei{}, \lca{}, \distance{}, \leafAny{}, \dfudsAny{}, \levelAny{}) were introduced by \cite{he2007succinct}

Many of the operation were later simplified by \cite{farzan2014uniform} with introduction of the better algorithm for tree decomposition.

We propose the operations \deepestVertex{} and \inAny{}.
We also show an alternative solutions to \hei{} and \levelFirst{} and \levelLast{}.
We further explicitly restrict the operations to the subtree of a given vertex.

\subsection{Decomposition Algorithm}

Instead of decomposing a bit string of the encoded tree, we decompose the tree and then we encode it.
Two decomposition algorithms have been proposed; they are parametrized by a target number of vertices $B$ to be present in a component.
The first algorithm \cite{geary2006succinct} decomposes the tree into connected components of size $[B, 3 B - 2]$ with the exception of the component containing the root, which can be undersized.
Such decomposition cannot exist unless the components are allowed to overlap; more specifically to overlap in their common root.
It follows from the bounds that there exist $O\left(\frac{n}{B}\right)$ components.

This decomposition was used and it leads to a succinct data structure which at the time of its introduction supported more operations than BP (child operations) or DFUDS (depth).
The problem of the decomposition was that the components were connected together in too many ways and the structure had to handle many cases.

Later a different decomposition was proposed in \cite{farzan2008uniform} with more details published in \cite{farzan2014uniform}.
It removes the lower bound on the sizes of the components while retaining their asymptotic number in exchange for restriction on the ways how the components can be connected with each other.
At most one edge from a non-root vertex connecting a different component is allowed.
Note that a stronger claim of no such edge existing does not provide a decomposition in a general case (e.g., a tree with depth greater than $2 B$).

\bigbreak

We present the latter decomposition since it results in components satisfying stronger properties.
A vertex is called \emph{heavy} if its subtree contains at least $B$ vertices.
All ancestors of a heavy vertex are heavy and therefore heavy vertices form a subtree $T_{\heavy}$ of the tree $T$.
A heavy vertex is called a \emph{branching vertex} if it has at least two heavy children, and \emph{branching edges} are called the edges connecting a branching vertex with its heavy children.

\begin{lemma}\label{l:no-branching}
	There are $O\left(\frac{n}{B}\right)$ branching vertices and branching edges in a tree $T$ with $n$ vertices.
\end{lemma}
\begin{proof}
	The tree $T_{\heavy}$ has at most $\frac{n}{B}$ leaves (we call them \emph{heavy leaves}) as each leaf is a root of a subtree of $T$ which contains at least $B$ vertices.
	Each branching vertex connects at least two heavy subtrees containing each at least one heavy leaf; therefore their number must be less than the number of all heavy leaves.
	The number of branching edges is the same as the number of heavy leaves plus the number of branching vertices minus one which can be seen after contraction of non-branching edges in the tree $T$.
\end{proof}

The decomposition is defined by an algorithm which processes the tree in DFS post-order; it first recursively processes all children of a vertex $v$ before solving $v$ itself.
A leaf starts its own \emph{temporary} component -- a component which has not been declared \emph{permanent}.
A set of permanent and at most one temporary component is returned from the recursion.
The way how the components are processed in $v$ depends on the number of its heavy children.

We distinguish three cases:
\begin{enumerate}
	\item If a vertex $v$ does not have any heavy children, then all children are parts of temporary components.
	Children are processed from left to right; their temporary components are merged with $v$ and potentially with the components of their right siblings.
	When the size of the current component is at least $B$, we declare it permanent and start the same process with the next temporary component if there is any.
	If at least one component was declared permanent, we declare all of them as permanent even though the last one can remain undersized.
	
	\item If a vertex $v$ has exactly one heavy child $u$, then we process it in a similar way as the case (1).
	If $u$ is part of a temporary component, nothing changes; otherwise we simply skip it.
	
	\item If a vertex $v$ has two or more heavy children ($v$ is a branching vertex), the temporary components containing the heavy children are declared permanent no matter what size they are.
	All non-heavy children are split into intervals delimited by the heavy children.
	Each interval is processed as in case (1) with the exception that all components are declared as permanent.
	If the vertex $v$ does not have any non-heavy children, then it forms a permanent component of size one.
\end{enumerate}

Several invariants hold during the course of the decomposition algorithm:
\begin{itemize}
	\item The size of a permanent component is less than $2 B - 2$; the size of a temporary component is less than $B$.
	A temporary component is only merged with another temporary components; it is declared permanent when its size is at least $B$.
	Because we merge a temporary component first with the parent and then with its right siblings one by one, its size will never be greater than $(B - 2) + 1 + (B - 1)$, at which point it is declared permanent.
	
	\item If a vertex is shared among multiple components, it is their common root.
	When such situation happens in the algorithm, all of them are declared as permanent and they are never dealt with again.
	
	\item Whenever a vertex $v$ is being processed and a component containing $v$ is declared permanent, then $v$ is a heavy vertex.
	In case (2) and (3) it is heavy from the fact that it is a parent of heavy children.
	In case (1) the first component is declared permanent if the components of children plus $v$ exceed $B$.
	If the first component is not declared permanent, none is.
	
	\item There is at most one edge leaving a component from a non-root vertex.
	A root $u$ of a permanent component which is connected by such edge is heavy from the previous invariant.
	Therefore, when the parent $v$ of $u$ is being processed, $u$ is its heavy child.
	If a component of another child of $v$ already contained such edge, then $v$ has at least two heavy children and case (3) applies.
	All components end with $v$ or its children, and so $u$ is connected to a root vertex instead of a non-root one.
	
	\item The number of all components is $O\left(\frac{n}{B}\right)$.
	We charge $O(1)$ undersized components to regular-sized components, branching edges, and branching vertices.
	The bound then follows from the lemma \ref{l:no-branching}.
	If an undersized component was declared permanent in (1) or (2), then another component of a regular size was declared too.
	In (3), it was either connected with an branching edge, or it happened once per interval of non-heavy children, which is delimited by at least one branching edge, or it is the branching vertex itself.
\end{itemize}

\bigbreak

We propose a modification of the algorithm which makes the resulting decomposition satisfy one more constraint.
In case (2), it could happen that the component of the heavy child $u$ is permanent, and some permanent components containing $v$ are created.
In such situation a left and a right sibling of $u$ could be in the same component, and thereby make the sequence of children of $v$ discontinuous in terms of component to which they belong.
Moreover, a heavy temporary component is forcefully declared permanent in case (3), which would lead to the same result.

We prevent this situation in case (2) to happen by splitting the children of $v$ into two intervals (one can be empty) and solving them separately similar to the case (3).
In case (3) we revise the temporary heavy component and split it in the same way; for that we return from recursion the vertex just before $u$.
This can result in at most two permanent undersized components which we charge to the permanent regular-sized component which was not created.
When the root is processed, a temporary component may need to be split.

\begin{lemma}\label{l:decompose-property}
	The components created by the altered decomposition algorithm satisfy the following property.
	Let $C$ be a sequence of components to which the children of a root of a component belong, then each component occurs in at most one run in $C$.
\end{lemma}
\begin{proof}
	The proof follows from the stated algorithm.
\end{proof}

\begin{algorithm}
\begin{algorithmic}
\Function{\decomposeSubtree}{$v, B$}
	\If{$\isLeaf(v)$}
		\State \Return{$[\,], v, -1$} \Comment{No permanent, itself as temporary, heavy children}
	\Else
		\State $P \gets [\,]$%
		\Instr $T \gets [\,]$ \Comment{All permanent and temporary from children}
		\State $R \gets[\,]$%
		\Instr $h \gets 0$ \Comment{Split vertices in children, number of heavy comps}
		\State $d \gets 0$ \Comment{Total size of temporary components}
		\ForAll{$u \gets \children(v)$}
			\State $(p, t, r') = \decomposeSubtree(u, B)$ \Comment{Process child}
			\State $\concatenate(P, p)$ \Comment{Gather permanent}
			\State $\append(T, t)$%
			\Instr $\append(R, r')$%
			\Instr $d \gets d + |t|$ \Comment{Store and count temp}
			\If{$\subtreeSize(u) \ge B$} \Comment{Count number of heavy children}
				\State $h \gets h + 1$
			\EndIf
		\EndFor
		\Statex
		
		\State $s \gets [v]$%
		\Instr $i \gets 0, r \gets -1$ \Comment{Working component}
		\ForAll{$(u, t, r') \gets \zip(\children(v), T, R)$}
			\If{$\subtreeSize(u) \ge B \booland |t| > 0 \booland h \ge 2$} \Comment{Heavy, temp, c. 3}
				\If{$r' \ne -1$} \Comment{Needs to be split}
					\State $s' \gets [\,]$
					\ForAll{$u' \gets t$} \Comment{Revise the component}
						\State $\append(s', u')$
						\If{$u' = r'$} \Comment{Split vertex found}
							\State $\append(P, s')$%
							\Instr $s' = [u]$ \Comment{Declare permanent, reset}
						\EndIf
					\EndFor
					\State $\append(P, s')$ \Comment{Declare permanent}
				\Else
					\State $\append(P, t)$ \Comment{Declare permanent}
				\EndIf
				\State $t \gets [\,]$ \Comment{$t$ has been processed}
			\ElsIf{$|t| = 0 \booland |s| > 1 \booland d > B$} \Comment{Heavy, perm, case 2, large}
				\State $\append(P, s)$%
				\Instr $s \gets [v]$%
				\Instr $i \gets i + 1$ \Comment{Declare permanent}
			\ElsIf{$|t| = 0$} \Comment{Heavy, permanent, case 2, small}
				\If{$\childFirst(v) \ne u \booland \childLast(v) \ne u$}
					\State $r \gets \childPrev(u)$ \Comment{Mark prev for potential splitting}
				\EndIf
			\EndIf
			\If{$|t| = 0 \booland |s| > 1 \booland h \ge 2$} \Comment{Permanent, non-empty $s$, case 3}
				\State $\append(P, s)$%
				\Instr $s \gets [v]$  \Comment{Declare permanent, reset}
			\ElsIf{$|t| \ne 0$} \Comment{Temporary}
				\State $\concatenate(s, t)$ \Comment{Merge $t$ into $s$}
				\If{$|s| \ge B$} \Comment{Regular sized}
					\State $\append(P, s)$%
					\Instr $s \gets [v]$%
					\Instr $i \gets i + 1$ \Comment{Declare permanent}
				\EndIf
			\EndIf
		\EndFor
		\Statex
		
		\If{$|s| = 1$}
			\State $s \gets [\,]$ \Comment{Reset before returning}
		\ElsIf{$i \ge 1 \boolor h \ge 2$} \Comment{At least one regular sized or case 3}
			\State $\append(P, s)$%
			\Instr $s \gets [\,]$ \Comment{Declare permanent}
		\EndIf
		\If{$h = \degree(v) \booland h \ge 2$} \Comment{All are heavy, case 3}
			\State $\append(P, [v])$ \Comment{Declare $v$ as permanent}
		\EndIf
		
		\State \Return{$P, s, r$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\Function{\decompose}{$v, B$}
	\State $(P, t, r) \gets \decomposeSubtree(v, B)$ \Comment{Decompose the subtree of root}
	\If{$|t| \ne 0$} \Comment{A temporary component exists}
		\If{$r = -1$}
			\State $\append(P, t)$ \Comment{Declare permanent}
		\Else \Comment{There is a split vertex}
			\State $s \gets [\,]$
			\ForAll{$u \gets t$} \Comment{Revise the component}
				\State $\append(s, u)$
				\If{$u = r$} \Comment{Split vertex found}
					\State $\append(P, s)$%
					\Instr $s = [u]$ \Comment{Declare permanent, reset}
				\EndIf
			\EndFor
			\State $\append(P, s)$ \Comment{Declare permanent}
		\EndIf
	\EndIf
	\State \Return{$P$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsection{The Structure}

We run the decomposition algorithm twice; the first time with $B = \log^c n$ for $c \ge 2$ which will be specified later.
The second time we decompose the components into small components with parameter $b = \frac{\log n}{8}$.
The components form connected subtrees in the tree, which we call mini-trees; similarly we call the subtrees in small components micro-trees.

There are three different connections between mini-trees (and similarly between micro-trees):
\begin{enumerate}
	\item Two mini-trees $s, t$ share their root vertex.
	The common root vertex can be shared among multiple mini-trees:
	$$\roott(s) = \roott(t).$$

	\item A parent of a root of a mini-tree $s$ is a root of a different mini-tree $t$.
	Either of the roots can be shared with other mini-trees:
	$$\parent(\roott(s)) = \roott(t).$$

	\item A parent of a root of a mini-tree $s$ (bottom) is a non-root vertex in a different mini-tree $t$ (top):
	$$\parent(\roott(s)) \in t \booland \parent(\roott(s)) \ne \roott(t).$$
	If this type of connection appears more than once in a mini-tree, then all bottom components share a common root.
\end{enumerate}

We define a set of terms for root related structures, which we use to refer to them without ambiguities.
A \emph{mini-tree root} is the root of a mini-tree.
A \emph{root mini-tree} is any mini-tree which contains the mini-tree root.
Similarly we define the terms for micro-trees where \emph{root micro-tree} refers to a micro-tree which contains a micro-tree root.
We also use negations, for example ``a micro-tree root of a non-root mini-tree''.

\subsubsection{Vertex Naming}

We order the mini-trees based on their pre-order number in the original tree.
For each pair of mini-trees $s, t$, the following properties hold:
\begin{enumerate}
	\item $\roott(s) \le \roott(t)$;
	\item If $\roott(s) = \roott(t)$, then their first children in the mini-trees are compared: $ \childFirst(\roott(s)) < \childFirst(\roott(t))$.
	Note that even though there are mini-trees with a single vertex, their roots are not shared.
\end{enumerate}

Each mini-tree is then assigned number $\tau_1$ based on this order.
The first mini-tree (it contains the tree root) is assigned the number $0$.
Similarly we assign a number $\tau_2$ to each micro-tree in a mini-tree $\tau_1$ and name the micro-tree $(\tau_1, \tau_2)$.
We continue with individual vertices in the same way; they are given a name $(\tau_1, \tau_2, \tau_3)$.

The size of $\tau_1$ is $O(\log n)$; the sizes of $\tau_2$ and $\tau_3$ are $O(\log \log n)$.
A vertex can be assigned multiple names when it is a common root of several micro-trees, which could even be in different mini-trees.
A \emph{canonical name} of a mini-tree, a micro-tree, or a vertex is the lexicographically smallest one.
The interface of all operations on the tree assumes that all names of vertices are canonical; non-canonical and partial names are used only for internal purposes of the data structure.

In order to handle the case (3) connection, we alter the process of decomposition of the tree.
After the mini-trees are identified by the decomposition algorithm, we subdivide each edge realizing the connection of type (3) by introducing a \emph{dummy vertex}, to which we refer as mini-tree dummy vertex.
This new vertex is then added to the top mini-tree, which increases its upper bound by one to $2 B - 1$.
Then we follow with the second level of the decomposition (mini-trees into micro-trees) and again introduce dummy vertices, to which we refer as micro-tree dummy vertices.

The total number of dummy vertices introduced is $O\left(\frac{n}{B} + \frac{n}{b}\right) = O\left(\frac{n}{\log n}\right)$.
The dummy vertex gets its name as if it was a normal vertex in the top mini-tree or micro-tree.
The canonical name of a dummy vertex is the canonical name of the vertex to which it is connected in the bottom mini-tree or micro-tree, which is its root.
The depth of a dummy vertex in a mini-tree or a micro-tree is at least $2$, because it has a parent which is not a root.

\bigbreak

We call \emph{primary} the mini-tree $\tau_1$ and the micro-tree $(\tau_1, \tau_2)$ which contains a root with a canonical name $(\tau_1, \tau_2, 0)$.
We also call primary the micro-tree $(\tau_1, 0, 0)$ so that every micro-tree has its primary micro-tree within the same mini-tree.
A root micro-tree can have two primary micro-trees: one within the same mini-tree, the other one in its primary mini-tree.
In the latter case we use the phrase ``in the primary mini-tree''.

The same way we numbered mini-trees we number primary mini-trees; we assign them $\sigma_1$ names.
We do the same for micro-trees with $\sigma_2$ names.
These names are only a technicality which is used to index structures which are stored in the tree structure instead of each primary mini-tree.

\subsubsection{Representation}

We use compressed arrays in two different settings throughout the whole data structure:
\begin{itemize}
	\item A single compressed array for all vertices in a mini-tree or a micro-tree with a bounded number of runs.
	
	Specifically, if we store $\tau_1$ names of all vertices of the tree requiring $O(1)$ runs per name, then the space is $O\left(\frac{n}{B} \log n\right) + o(n) = o(n)$ bits.
	Similarly for $\tau_2$ names of vertices of a given mini-tree, the space complexity is $O\left(\frac{B}{b} \log B\right) + o(B) = o(B)$ bits.
	
	\item A collection of $O(r)$ compressed arrays $A_i$, containing $a$ elements of size $s$ in $r$ runs in total.
	
	If each $\tau_1$ name occurs in $O(1)$ arrays in $O(1)$ runs, and there is at most one record for each vertex of the tree, then the space complexity is the same as in the previous case.
	The same applies for $\tau_2$ names within a given mini-tree.
\end{itemize}

For each micro-tree we store several pieces of information:
\begin{description}
	\item[Identity of the micro-tree]
	Information about the position of the micro-tree within the mini-tree.
	\begin{description}
		\item[$\tau_2$]
		Its $\tau_2$ name; if the name equals to $0$, it is a root micro-tree.
		
		\item[$\offset$]
		The offset of this structure from the beginning of the structure of the mini-tree in bits.
		While $\tau_1$ name is too big, the offset is at most $B + o(B)$, which results in $\log \log n$ bits.
		In order to move to the mini-tree structure, we subtract the $\offset$ from the position where the micro-tree structure begins.
		
		\item[$\primaryII$]
		The $\tau_2$ name of the primary micro-tree; it can be the micro-tree itself.
		
		\item[$\sigma_2$]
		The $\sigma_2$ name of the primary micro-tree.
	\end{description}

	\item[Parent and the dummy vertex]
	Each micro-tree can have a parent micro-tree and can contain a dummy vertex which leads to another mini-tree or micro-tree.
	\begin{description}
		\item[$\parentII$]
		The $\tau_2$ name of the primary micro-tree which contains its parent.
		The parent could in theory be stored only in the structure of its primary micro-tree, however, it is small enough to keep a copy in all of them.
		
		\item[$\typeIII$]
		A boolean denoting whether it is connected to its parent micro-tree by a type (3) connection.
		
		\item[$\dummyII$]
		The $\tau_3$ name of the dummy vertex which represents the type (3) connection to a different micro-tree.
		The value $-1$ means that the micro-tree does not have a dummy vertex.
		
		\item[$\bottomII$]
		The $\tau_2$ name of the primary micro-tree to which the dummy vertex leads.
		If $\dummyII \ne -1 \booland \bottomII = -1$, then the dummy vertex leads to a different mini-tree, which is handled by the mini-tree structure.
	\end{description}
	
	\item[Children]
	Since the structure storing children is a collection of compressed arrays, it is stored on a mini-tree level.
	Here we store only fields which are useful for determining \childRank.
	\begin{description}
		\item[$\childrenIndexII$]
		The index of the first occurrence of $\tau_2$ within the compressed array of the children for the primary micro-tree.
		
		\item[$\childrenParentII$]
		The index of the first occurrence of $\tau_2$ within the compressed array of the children for the parent's micro-tree.
		This index is $-1$ if $\typeIII = \true$ because in such case the micro-tree root is not a child of parent's micro-tree root.
	\end{description}
	
	\item[Representation]
	All look-up tables will take the following two fields as their arguments.
	\begin{description}
		\item[$\size$]
		The number of vertices $k$ of the micro-tree; this includes the possibly shared root and the dummy vertex.
		
		\item[$\rep$]
		The succinct (or even implicit) representation of the micro-tree which uses $2k$ bits.
	\end{description}
\end{description}

All fields except for $\rep$ require only $O(\log \log n)$ bits per micro-tree.
The succinct representations $\rep$ of all micro-trees together contain all $n$ vertices of the tree together with $o(n)$ dummy vertices and $o(n)$ shared root vertices.
The representations require $2n + o(n)$ bits in total and are the dominant part of the structure.

Each micro-tree contains $k$ vertices, with an upper bound of $ k \le 2b - 1 < \frac{\log n}{4}$ vertices.
We can represent this subtree succinctly using $2k < \frac{\log n}{2}$ bits, which is small enough to be used as an index to a look-up table.
All our look-up tables will require space $o(n)$.

\bigbreak

The structure for a mini-tree is similar to the micro-tree structure.
The only difference is that it contains the collection of compressed arrays for roots of micro-trees.
\begin{description}
	\item[Identity of the mini-tree]
	\begin{description}
		\item[]
		
		\item[$\tau_1$]
		Its $\tau_1$ name.

		\item[$\primaryI$]
		The $\tau_1$ name of the primary mini-tree; it can be the mini-tree itself.
		
		\item[$\sigma_1$]
		The $\sigma_1$ name of the primary mini-tree.
	\end{description}

	\item[Parent and the dummy vertex]
	\begin{description}
		\item[]

		\item[$\parentI$]
		The $\tau_1$ name of the mini-tree which contains the parent of the root of this mini-tree.
		
		\item[$\dummyI$]
		The $\tau_2$ name of the micro-tree which contains the dummy vertex which was introduced for edges between mini-trees.
		If there is no mini-tree dummy vertex, then it is $-1$.
		
		\item[$\bottomI$]
		The $\tau_1$ name of the mini-tree to which the micro-tree dummy vertex leads, or $-1$.
	\end{description}
	
	\item[Children]
	\begin{description}
		\item[]

		\item[$\childrenII$]
		A collection of compressed arrays containing one array per a primary micro-tree.
		Each array contains $\tau_2$ names of children of the micro-tree root restricted to the current mini-tree.
		Individual parts of the collection are accessed by $\sigma_2$ names of the micro-trees.
		
		\item[$\childrenIndexI$]
		The index of the first occurrence of $\tau_1$ within the compressed array of the children for the primary mini-tree.
		
		\item[$\childrenParentI$]
		The index of the first occurrence of $\tau_1$ within the compressed array of the children for the parent's mini-tree.
		This index is $-1$ if $\typeIII = \true$.
	\end{description}
	
	\item[Representation]
	\begin{description}
		\item[]
	
		\item[$\microTreeOffsets$]
		A table of offsets of the micro-tree structures, as in lemma \ref{l:concat}.
		
		\item[$\microTrees$]
		The micro-tree structures stored consecutively.
	\end{description}
\end{description}

All fields except for $\childrenII$ and the representation, require $O(\log n)$ bits of space.
The collection of compressed arrays $\childrenII$ satisfies the property stated earlier since:
\begin{enuminline}
	\item each vertex (and each micro-tree) is a child of at most one root;
	\item all occurrences of $\tau_2$ form a single run which follows from our modification of the decomposition algorithm.
\end{enuminline}

\bigbreak

At the global level, we only need a very simple structure:
\begin{description}
	\item[Children]
	\begin{description}
		\item[]
		\item[$\childrenI$]
		The same structure as $\childrenII$ in mini-trees: each array contains $\tau_1$ names of children of a mini-tree root.
	\end{description}

	\item[Representation]
	\begin{description}
		\item[]
	
		\item[$\miniTreeOffsets$]
		A table of offsets of the mini-tree structures, as in lemma \ref{l:concat}
		
		\item[$\microTrees$]
		The mini-tree structures stored consecutively.
	\end{description}
\end{description}

\subsection{Navigation Operations}

With the structure which we have just described, the navigation operations can already be supported.
In the presented algorithms we identify the structures with their names provided that we can navigate to them:
\begin{description}
	\item[global $\to$ mini-tree $\tau_1$] using $\miniTreeOffsets$ and $\miniTrees$;
	\item[mini-tree $\tau_1$ $\to$ micro-tree $(\tau_1, \tau_2)$] using $\microTreeOffsets$ and $\microTrees$;
	\item[micro-tree $(\tau_1, \tau_2)$ $\to$ mini-tree $\tau_1$] using $\offset$;
	\item[mini-tree $\tau_1$ $\to$ global] it simply starts at position $0$.
\end{description}

Since individual vertices do not have a structure on their own, then we use a vertex name $i = (\tau_1, \tau_2, \tau_3)$ to access the micro-tree $(\tau_1, \tau_2)$.
We assume that mini-trees have access to all global fields, and all micro-trees have access to all mini-tree and global fields.

\subsubsection{Helper Functions}

We define three helper functions which traverse the edge of type (3) and canonize the name of a vertex.
As they are not part of the interface of the data structure, the argument $i$ is allowed to be a non-canonical name.

\begin{algorithm}
\begin{algorithmic}
\Function{\dummyUp}{$i$}
	\If{$i.\tau_3 = 0 \booland i.\typeIII$} \Comment{If root and type (3) connected}
		\If{$i.\tau_2 \ne 0$} \Comment{Micro-tree dummy vertex}
			\State \Return{$(i.\tau_1, \parentII, \parentII.\dummyII)$}
		\Else \Comment{Mini-tree dummy vertex}
			\State \Return{$(i.\parentI, i.\parentI.\dummyI, i.\parentI.\dummyI.\dummyII)$}
		\EndIf
	\Else \Comment{Idempotent otherwise}
		\State \Return{$i$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\Function{\dummyDown}{$i$}
	\If{$i.\tau_3 = i.\dummyII$} \Comment{This is a dummy vertex}
		\If{$i.\bottomII \ne -1$} \Comment{Micro-tree dummy vertex}
			\State \Return{$(i.\tau_1, i.\bottomII, 0)$}
		\Else \Comment{Mini-tree dummy vertex}
			\State \Return{$(i.\bottomI, 0, 0)$}
		\EndIf
	\Else \Comment{Idempotent otherwise}
		\State \Return{$i$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\Function{\canonize}{$i$}
	\If{$i.\tau_3 \ne 0$} \Comment{Potentially dummy vertex}
		\State \Return{$\dummyDown(i)$}
	\ElsIf{$i.\primaryII \ne 0$} \Comment{Not a root micro-tree}
		\State \Return{$(i.\tau_1, i.\primaryII, 0)$}
	\Else \Comment{Potentially shared with different mini-tree}
		\State \Return{$(j.\primaryI, 0, 0)$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

We add four more functions which navigate to special vertices in a given micro-tree or a mini-tree.
Their names alias with the fields in the representation, however they can always be distinguished by the parentheses.
The function can also be called with mini-tree name or a micro-tree name.
The last four functions assume that such dummy vertex exists.
\begin{align*}
	\rootI(i) &= \canonize(i.\tau_1, 0, 0) \\
	\rootII(i) &= \canonize(i.\tau_1, i.\tau_2, 0) \\
	\dummyI(i) &= (i.\tau_1, i.\dummyI, i.\dummyI.\dummyII) \\
	\dummyII(i) &= (i.\tau_1, i.\tau_2, i.\dummyII) \\
	\bottomI(i) &= \dummyDown(\dummyI(i)) \\
	\bottomII(i) &= \dummyDown(\dummyII(i))
\end{align*}

\bigbreak

The operations \isRoot{} and \isLeaf{} use the property that $i$ is a canonical name.
If $i$ is a root of the tree, it is part of the primary root mini-tree, which in pre-order numbering has the number $0$.
We apply the same reasoning on micro-trees inside the mini-tree and to the vertex inside the micro-tree.

Similarly, because of the canonicity, $i$ cannot be the name of a dummy vertex inside the top micro-tree.
The \degree{} look-up table used in \isLeaf{} can therefore be oblivious of the existence of dummy vertices.

\begin{algorithm}
\begin{algorithmic}
\Function{\isRoot}{$i$}
	\State \Return{$i = (0, 0, 0)$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\Function{\isLeaf}{$i$}
	\State \Return{$\degree[i.\size, i.\rep, i.\tau_3] = 0$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Parent}

A vertex can potentially use a connection of type (3) to its parent; we handle that by utilizing the \dummyUp{} function.
Then we continue differently in cases of a non-root, a micro-tree root but not a mini-tree root, a mini-tree root, and the tree root.
This pattern of four cases will keep recurring in most of our algorithms.

If the $i$ is not a micro-tree root ($\tau_3 \ne 0$), we use a look-up table to obtain the answer.
If it is a micro-tree root ($\tau_3 = 0$) but not a mini-tree root ($\tau_2 \ne 0$), then the parent is present in a micro-tree $\parentII$ within the same mini-tree.
If the vertex is a mini-tree root, but not the root of the whole tree ($\tau_2 = 0 \booland \tau_1 \ne 0$), the answer is the root of the parent mini-tree.
The last case of the tree root vertex $(0, 0, 0)$ simply leads to a failure.

\begin{algorithm}
\begin{algorithmic}
\Function{parent}{$i$}
	\State $i \gets \dummyUp(i)$ \Comment{Handles type (3) connection}
	\If{$i.\tau_3 \ne 0$} \Comment{Non-root}
		\State \Return{$(i.\tau_1, i.\tau_2, \parent[i.\size, i.\rep, i.\tau_3])$} \Comment{Same micro-tree}
	\ElsIf{$i.\tau_2 \ne 0$} \Comment{Micro-tree root but not mini-tree root}
		\State \Return{$(i.\tau_1, i.\parentII, 0)$} \Comment{Same mini-tree}
	\ElsIf{$i.\tau_1 \ne 0$} \Comment{Mini-tree root but not tree root}
		\State \Return{$(i.\parentI, 0, 0)$}
	\Else \Comment{Tree root}
		\State \Return{$-1$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Children}

We solve all operations on children of a vertex $i$ (\degree{}, \childRank{} and \childSelect{}) using the compressed arrays $\childrenI$ and $\childrenII$.

\begin{algorithm}
\begin{algorithmic}
\Function{\degree}{$i$}
	\If{$i.\tau_3 \ne 0$}
		\State \Return{$\degree[i.\size, i.\rep, i.\tau_3]$}
	\ElsIf{$i.\tau_2 \ne 0$}
		\State \Return{$\size(i.\childrenII, i.\sigma_2)$}
	\Else
		\State \Return{$\size(i.\childrenI, i.\sigma_1)$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

The \childRank{} algorithm starts with  identifying where the current micro-tree is located in the compressed array of children of $p$; for this we have stored indices $\childrenIndexBoth$ and $\childrenParentBoth$ in the representation.
Their alternative meaning is that they represent the number of children before the current mini-tree or micro-tree.
Note that we use the property from lemma \ref{l:decompose-property}.

Two cases need to be distinguished:
\begin{enuminline}
	\item the parent $p$ is within the same micro-tree,
	\item or its is in a different micro-tree.
\end{enuminline}
If $p$ is a mini-tree root, we follow the same procedure first on a mini-tree level, then on a micro-tree level.
Finally, we use a look-up table to find the \childRank{} within a micro-tree.

\begin{algorithm}
\begin{algorithmic}
\Function{\childRank}{$i$}
	\State $p \gets \parent(i)$
	\State $i \gets \dummyUp(i)$ \Comment{Handling of type (3) connection}
	\If{$p.\tau_3 \ne 0$}
		\State \Return{$\childRank[p.\size, p.\rep, i.\tau_3]$}
	\ElsIf{$p.\tau_2 \ne 0$}
		\If{$i.\primaryII = p.\tau_2$} \Comment{Connection type (1) between micro-trees}
			\State \Return{$i.\childrenIndexII + \childRank[i.\size, i.\dep, i.\tau_3]$}
		\Else \Comment{Connection type (2) between micro-trees}
			\State \Return{$i.\childrenParentII + 1$}
		\EndIf
	\ElsIf{$p.\tau_1 \ne 0$}
		\If{$i.\primaryI = p.\tau_1$} \Comment{Connection type (1) between mini-trees}
			\If{$i.\primaryII = p.\tau_2$} \Comment{Connection type (1) between micro-trees}
				\State $r \gets \childRank[i.\size, i.\dep, i.\tau_3]$
				\State \Return{$i.\childrenIndexI + i.\childrenIndexII + r$}
			\Else \Comment{Connection type (2) between micro-trees}
				\State \Return{$i.\childrenIndexI + i.\childrenParentII + 1$}
			\EndIf
		\Else \Comment{Connection type (2) between mini-trees}
			\State \Return{$i.\childrenParentI + 1$}
		\EndIf
	\Else
		\State \Return{$-1$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

The algorithm \childSelect{} introduces a pattern which will be often used in other operations.
When $i$ is a mini-tree root, we first find the mini-tree which contains the $k$-th child, and the offset $k'$ within the mini-tree.
We follow in the same way with micro-trees.
Finally we solve the query within a micro-tree using a look-up table.

\begin{algorithm}
\begin{algorithmic}
\Function{\childSelect}{$i, k$}
	\If{$i.\tau_3 \ne 0$}
		\State $d \gets \childSelect[i.\size, i.\rep, i.\tau_3, k]$
		\State \Return{$\dummyDown(d)$}
	\ElsIf{$i.\tau_2 \ne 0$}
		\State $d \gets i.\childrenII[k - 1]$
		\State $k' \gets \rank(i.\childrenII, k - 1)$
		\If{$d.\primaryII = i.\tau_2$} \Comment{Connection type (1) between micro-trees}
			\State \Return{$\childSelect[d.\size, d.\rep, 0, k']$}
		\Else \Comment{Connection type (2) between micro-trees}
			\State \Return{$(i.\tau_1, d, 0)$}
		\EndIf
	\Else
		\State $d_1 \gets i.\childrenI[k - 1]$
		\State $k' \gets \rank(i.\childrenI, k - 1)$
		\If{$d_1.\primaryI = i.\tau_1$} \Comment{Connection type (1) between mini-trees}
			\State $d_2 \gets d_1.\childrenII[k' - 1]$
			\State $k'' \gets \rank(d_1.\childrenII, k' - 1)$
			\If{$d_2.\primaryII = i.\tau_2$} \Comment{Connection type (1) between micro-trees}
				\State \Return{$\childSelect[d_2.\size, d_2.\rep, 0, k'']$}
			\Else \Comment{Connection type (2) between micro-trees}
				\State \Return{$(d_1, d_2, 0)$}
			\EndIf
		\Else \Comment{Connection type (2) between mini-trees}
			\State \Return{$(d_1, 0, 0)$}
		\EndIf
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsection{Depth, Deepest Vertex, Height, Subtree-Size}

In order to support more operations we need to augment the structure with more information.
Here we focus on operations which return information about vertices.

\begin{description}
	\item[Micro-tree]
	The micro-tree structure is augmented with the following fields:
	\begin{description}
		\item[$\depthII$]
		The depth of the micro-tree root within the mini-tree, which is the distance from the mini-tree root.
		
		\item[$\dummyAncestor$]
		A boolean flag denoting whether the micro-tree root is an ancestor of a mini-tree dummy vertex.
		
		\item[$\subtreeSizeII$]
		The size of the subtree of the micro-tree root excluding any type (3) connected mini-tree.
		
		\item[$\deepestVertexII$]
		The $(\tau_2, \tau_3)$ name of the deepest vertex within the subtree restricted to the current mini-tree.
		It is often a mini-tree dummy vertex.
	\end{description}
	
	\item[Mini-tree]
	The mini-tree structure contains information about the mini-tree root and its subtree.
	\begin{description}
		\item[$\depthI$] 
		The depth of the mini-tree root within the whole tree.
		
		\item[$\subtreeSizeI$]
		The full size of the subtree.
		
		\item[$\deepestVertexI$]
		The full name of the deepest vertex within the subtree.
	\end{description}
\end{description}

The operation \dep{} is straightforward; it sums
\begin{iteminline}
	\item the micro-tree-local depth of the vertex,
	\item mini-tree-local depth of the micro-tree root,
	\item and the global depth of the mini-tree root.
\end{iteminline}

\begin{algorithm}
\begin{algorithmic}
\Function{\dep}{$i$}
	\If{$i.\tau_3 \ne 0$}
		\State \Return{$\dep(\rootII(i)) + \dep[i.\size, i.\rep, i.\tau_3]$}
	\ElsIf{$i.\tau_2 \ne 0$}
		\State \Return{$\dep(\rootI(i)) + i.\depthII$}
	\Else
		\State \Return{$i.\depthI$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

The operation \deepestVertex{} is more complex than \dep{}.

If $i$ is a non-root, we find the deepest vertex using a look-up table.
We also consider the alternative that the deepest vertex is present in the subtree which is connected via a dummy vertex, if $i$ is its ancestor.
The recursive call reduces the search to one of the following cases.

If $i$ is a micro-tree root but not a mini-tree root, then if it is not a dummy vertex, we answer with $\deepestVertexII$, otherwise we follow the connection to a mini-tree root and solve the query there.
If $i$ is a mini-tree root, we answer immediately with the stored vertex $\deepestVertexI$.

\begin{algorithm}
\begin{algorithmic}
\Function{\deepestVertex}{$i$}
	\If{$i.\tau_3 \ne 0$}
		\State $d \gets (i.\tau_1, i.\tau_2, \deepestVertex[i.\size, i.\rep, i.\tau_3])$ \Comment{Within micro-tree}
		\If{$\isAncestor[i.\size, i.\rep, i.\tau_3, i.\dummyII]$} \Comment{Type (3) connection?}
			\State $d' \gets \deepestVertex(\bottomII(i))$ \Comment{Outside}
			\If{$d.\tau_3 = i.\dummyII$}
				\State \Return{$d'$}
			\Else
				\State \Return{$\textif \dep(d) > \dep(d') \textthen d \textelse d'$} \Comment{The deeper one}
			\EndIf
		\Else
			\State \Return{$d$}
		\EndIf
	\ElsIf{$i.\tau_2 \ne 0$}
		\State $d \gets (i.\tau_1, i.\deepestVertexII.\tau_2, i.\deepestVertexII.\tau_3)$
		\If{$d.\tau_3 = d.\dummyII$} \Comment{Mini-tree dummy vertex?}
			\State \Return{$\deepestVertex(\dummyDown(d))$} \Comment{Recursion}
		\Else
			\State \Return{$d$}
		\EndIf
	\Else
		\State \Return{$i.\deepestVertexI$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

The operation \deepestVertex{} is also used for supporting of \hei{}.

\begin{algorithm}
\begin{algorithmic}
\Function{\hei}{$i$}
	\State $d \gets \deepestVertex(i)$
	\State \Return{$\dep(d) - \dep(i)$}
\EndFunction
\end{algorithmic}
\end{algorithm}

The operation \subtreeSize{} is similar to \deepestVertex{}
The answer is known for a mini-tree root.
In case of a micro-tree root, we know the subtree size restricted to the mini-tree; we sum it with the subtree size of a potentially type (3) connected mini-tree if it exists in the subtree of $i$.
Finally, in case of a non-root, we use a look-up table, plus we add the size of anything connected by a dummy vertex, and we subtract $1$ for the dummy vertex.

\begin{algorithm}
\begin{algorithmic}
\Function{\subtreeSize}{$i$}
	\If{$i.\tau_3 \ne 0$}
		\State $s \gets \subtreeSize[i.\size, i.\rep, i.\tau_3]$
		\If{$\isAncestor[i.\size, i.\rep, i.\tau_3, i.\dummyII]$}
			\State \Return{$s - 1 + \subtreeSize(\bottomII(i))$}
		\Else
			\State \Return{$s$}
		\EndIf
	\ElsIf{$i.\tau_2 \ne 0$}
		\If{$i.\dummyAncestor$}
			\State \Return{$i.\subtreeSizeII + \subtreeSize(i.\bottomI, 0, 0)$}
		\Else
			\State \Return{$i.\subtreeSizeII$}
		\EndIf
	\Else
		\State \Return{$i.\subtreeSizeI$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsection{Vertex and Leaf Ranks and Selects}

We again augment the global structure and the structures of mini-trees and micro-trees with additional data to support new operations.
We consider four distinct vertex numbering schemas and later use the same techniques to support operations on leaves restricted to a subtree.

It is crucial to account every vertex of the original tree once; we do so by introducing a relation \emph{to belong to}.
We define the relation differently for each numbering schema.

\subsubsection{Pre-Order Numbering}

A vertex $i$ with a canonical name $(\tau_1, \tau_2, \tau_3)$ belongs to a mini-tree $\tau_1$ and a micro-tree $(\tau_1, \tau_2)$.
Each vertex of the original tree belongs to exactly one mini-tree and one micro-tree.

A vertex in a mini-tree or a micro-tree is called the \emph{first} if is belongs to the mini-tree or micro-tree and has the lexicographically smallest name.
We can find it by asking if the root belongs to the mini-tree or the micro-tree; if not, we set $\tau_3 = 1$.
Note that there can exist a micro-tree consisting of a single vertex, which is its root, that is shared with another micro-trees; in such case, the first vertex is undefined.

\bigbreak

We store the explicit pre-order number $\preFirstI$ of the first vertex of each mini-tree.
We store the offset of the pre-order number $\preFirstII$ from $\preFirstI$ for the first vertex of each micro-tree while skipping the possible mini-tree connected via the type (3) connection.

When we compute the \preRank{}, we need to determine which vertex is the first one in a mini-tree (micro-tree); this is achieved by comparing the canonical name of  its root with the name of the name of the mini-tree (micro-tree).

If $i$ is the first vertex in a mini-tree, we answer the query directly.
If $i$ is the first vertex in a micro-tree, we add its offset to the first vertex in the mini-tree, and also the subtree size of a possible type (3) connected mini-tree if it is before the current micro-tree.
Otherwise, we determine the offset of $i$ from the first vertex within the micro-tree and add compensate for the dummy vertex and its subtree if it is in the micro-tree before $i$.

We state the algorithm in a more general form which does not assume that the \preRank{} corresponds to the names of vertices; it will make the discussion of \postRank{} easier.
The look-up table \preRank{} has one additional argument which makes sure that the rank is counted from the first vertex in the micro-tree.

\begin{algorithm}
\begin{algorithmic}
\Function{\preRank}{$i$}
	\State $\first_1 \gets (i.\tau_1, 0, i.\tau_1 \ne i.\primaryI)$
	\State $\first_2 \gets (i.\tau_1, i.\tau_2, i.\tau_2 \ne i.\primaryII \boolor (i.\tau_1 \ne i.\primaryI \booland i.\tau_2 = 0))$
	\If{$i = \first_1$} \Comment{First in mini-tree}
		\State $r \gets i.pre\_first_1$
	\ElsIf{$i = \first_2$} \Comment{First in micro-tree}
		\State $r \gets i.\first_2$
		\If{$i.\dummyI \ne -1 \booland i.\dummyI.\preFirstII < r$}
			\State $d \gets \bottomI(i)$
			\State $r \gets r + \subtreeSize(d)$ \Comment{Type (3) connected mini-tree}
		\EndIf
		\State $r \gets r + \preRank(\first_1)$
	\Else \Comment{Non-first}
		\State $r \gets \preRank[i.\size, i.\rep, i.\tau_3, \first_2.\tau_3]$
		\If{$i.\dummyII \ne -1 \booland \preRank[i.\size, i.\rep, i.\dummyII, \first_2.\tau_3] < r$}
			\State $d \gets \bottomII(i)$
			\State $r \gets r + \subtreeSize(d)$ \Comment{Type (3) connection}
		\EndIf
		\State $r \gets r + \preRank(\first_2)$
	\EndIf
	
	\State \Return{$r$}
\EndFunction
\end{algorithmic}
\end{algorithm}

We store a compressed array $\preVerticesI$ of $\tau_1$ names for all vertices of the tree in pre-order; each vertex reports the $\tau_1$ name of the mini-tree to which it belongs.
The space complexity of $o(n)$ bits comes from the following lemma and the discussion in the beginning of the representation.

\begin{lemma}
	Each $\tau_1$ name is the compressed array $\preVerticesI$ occurs in at most three runs.
\end{lemma}
\begin{proof}
	We describe all situation which can lead to the sequence being split into multiple runs.
	\begin{enumerate}
		\item A root vertex of a mini-tree can have type (2) connected mini-tree which appear before all its children.
		\item A dummy vertex introduces an alien subtree inside the current one.
	\end{enumerate}
\end{proof}

We store a similar compressed array $\preVerticesII$ of $\tau_2$ names for each mini-tree; only the vertices belonging to the mini-tree are reported.
The space complexity is $o(B)$ bits per mini-tree.

In the search, we first find the correct mini-tree and the remaining $r'$ within it; then the correct micro-tree and the remaining $r''$.
In the end, we use a look-up table in the micro-tree with correction for the non-root first vertex and the possible dummy vertex.
We can ignore type (3) connections as they were taken care of implicitly by the compressed arrays.

\begin{algorithm}
\begin{algorithmic}
\Function{\preSelect}{$r$}
	\State $d_1 \gets \preVerticesI[r - 1]$ \Comment{Name of the mini-tree}
	\State $r' \gets \rank(\preVerticesI, r - 1)$

	\State $d_2 \gets d_1.\preVerticesII[r' - 1]$ \Comment{Name of the micro-tree}
	\State $r'' \gets \rank(d_1.\preVerticesII, r' - 1)$
	
	\Statex
	
	\State $\first_2 \gets (i.\tau_1, i.\tau_2, i.\tau_2 \ne i.\primaryII \boolor (i.\tau_1 \ne i.\primaryI \booland i.\tau_2 = 0))$
	\If{$\preRank[d_2.\size, d_2.\rep, d_2.\dummyII, \first_2.\tau_3] \le r''$}
		\State $r'' \gets r'' + 1$ \Comment{Add the dummy vertex because of the table look-up}
	\EndIf
	
	\State \Return{$\canonize(d_1, d_2, \preSelect[d_2.\size, d_2.\rep, r'', \first_2.\tau_3])$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Ancestor Checking}

We have already use a look-up table called \isAncestor{} which solved this query for vertices in a micro-tree.
This table was used in the operation \subtreeSize{} which is used in \preRank{} which is used for defining the general \isAncestor{} operation.

\begin{algorithm}
\begin{algorithmic}
\Function{\isAncestor}{$i_1, i_2$}
	\State \Return{$\preRank(i_1) \le \preRank(i_2) \le \preRank(i_1) + \subtreeSize(i_1) - 1$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Post-Order Numbering}

The \postRank{} and \postSelect{} are very similar to \preAny{}, however there are several differences which make them more complicated.

We use a different definition of belonging -- a vertex belongs to the mini-tree and micro-tree with the lexicographically biggest name instead of the smallest one; we call them the \emph{terminary mini-tree and micro-tree}.
We introduce an analogy of the fields $\primaryI$ and $\primaryII$ called $\terminaryI$ and $\terminaryII$ which are used to navigate to the terminary mini-tree and micro-tree from the primary ones.

Since the first vertex which is assigned a post-order number in a mini-tree or micro-tree is its first leaf which could also be a dummy vertex, we store the explicit ($\postLastI$) or offsetted ($\postLastII$) post-order ranks of the last vertices in the mini-tree or a micro-tree.
The value of $\postLastII$ is non-positive.
Variables $\last_1$ and $\last_2$ are defined similarly to $\first_1$ and $\first_2$ using the definition of belonging.

We omit the algorithms here because they differ only in details.

\subsubsection{DFUDS-Order Numbering}

\begin{lemma}
	The DFUDS-order number of a vertex can be determined by a recursive formula:

	\begin{align*}
		\dfudsAnc(i) &= \sum_{a \in \ancestors(i) \setminus \{i\}} |\rightSiblings(a)|, \\
		\dfudsRank(i) &=
		\begin{cases}
			1 & \textif \isRoot(i); \\
			\preRank(i) + \dfudsAnc(i)  & \textif \childRank(i) = 1; \\
			\!\begin{aligned}
				&\dfudsRank(\childFirst(\parent(i))) \\
				&\ + \childRank(i) - 1
			\end{aligned} & \textotherwise.
		\end{cases}
	\end{align*}
\end{lemma}

Finding the \dfudsRank{} of a non-first child is easy and does not require any special consideration.
In case of the first child, we already know its \preRank{} so the only thing left is to compute \dfudsAnc{} in constant time.

Let $v_1$ and $v_2$ be ancestors of $i$ such that:
\begin{align*}
	v_1 \in \ancestors(i) &\booland \parent(v_1) = \rootI(i), \\
	v_2 \in \ancestors(i) &\booland \parent(v_2) = \rootII(i).
\end{align*}

We split the precomputed $\dfudsAnc(i)$ into several parts, which are in the most general case:
\begin{alignat}{2}
	\dfudsAnc(i) &= \dfudsAnc(\parent(v_1)) \tag{A}\\
	&\qquad + \dfudsAnc(v_1) &&- \dfudsAnc(\parent(v_1)) \tag{B}\\
	&\qquad + \dfudsAnc(\parent(v_2)) &&- \dfudsAnc(v_1) \tag{C}\\
	&\qquad + \dfudsAnc(v_2) &&- \dfudsAnc(\parent(v_2)) \tag{D}\\
	&\qquad + \dfudsAnc(i) &&- \dfudsAnc(v_2). \tag{E}
\end{alignat}

If $v_1 = v_2$, then $C$ and $D$ do not exist.

When we refer to the mini-tree structure, it is $i.\tau_1$; the micro-tree structure is $(i.\tau_1, i.\tau_2)$.
\begin{description}
	\item[$A$]
	It is the answer for a mini-tree root; it is stored in the mini-tree structure.
	
	\item[$B$]
	Reduced to the number of right siblings of a mini-tree root; stored in the mini-tree structure.
	
	\item[$C$]
	Since the right siblings of $v_1$ can span over multiple mini-trees, we split $C$ into two parts $C_1 + C_2 = C$ such that:
	\begin{align*}
		C_1 &= \sum_{a \in \ldots} |\{ s : s \in \rightSiblings(a) \booland s.\tau_1 \ne a.\tau_1 \}|, \\
		C_2 &= \sum_{a \in \ldots} |\{ s : s \in \rightSiblings(a) \booland s.\tau_1 = a.\tau_1 \}|.
	\end{align*}
	$C_1$ is stored in the mini-tree structure; $C_2$ in the micro-tree structure.
	
	\item[$D$]
	Reduced to the number of right siblings of a micro-tree root; stored in a micro-tree structure.
	As the micro-tree root is not a mini-tree root, all its right siblings are in the same mini-tree.
	
	\item[$E$]
	The value $E$ cannot be fully computed by a look-up table since it account for vertices which can be outside the micro-tree and even outside the mini-tree.
	We split it into three parts $E_1 + E_2 + E_3 = E$ such that:
	\begin{align*}
		E_1 &= \sum_{a \in \ldots} |\{ s : s \in \rightSiblings(a) \booland s.\tau_1 \ne a.\tau_1 \}|, \\
		E_2 &= \sum_{a \in \ldots} |\{ s : s \in \rightSiblings(a) \booland s.\tau_1 = a.\tau_1 \booland s.\tau_2 \ne a.\tau_2 \}|, \\
		E_3 &= \sum_{a \in \ldots} |\{ s : s \in \rightSiblings(a) \booland s.\tau_1 \ne a.\tau_1 \booland s.\tau_2 = a.\tau_2  \}|.
	\end{align*}
	
	$E_1$ is stored in the mini-tree structure; $E_2$ in the micro-tree structure; $E_3$ is provided by a look-up table.
	Note that $E_1$ needs to be stored only for root micro-trees, and that it has the same value for all of them within the same mini-tree.
\end{description}

The algorithm for the operation \dfudsRank{} consists mostly of the computation of \dfudsAnc{}.
Six cases of the position of the vertex $i$ in the tree has to be considered.

\begin{algorithm}
\begin{algorithmic}
\Function{\dfudsRank}{$i$}
	\If{$\isRoot(i)$}
		\State \Return{$1$}
	\ElsIf{$\childRank(i) > 1$}
		\State \Return{$\dfudsRank(\childFirst(\parent(i))) + \childRank(i) - 1$}
	\Else
		\State $s \gets \preRank(i)$
		\If{$i.\tau_3 \ne 0$}
			\State $p \gets \parent(i)$
			\If{$p.\tau_3 \ne 0$}
				\State $r \gets \rootII(i)$
				\If{$r.\tau_2 \ne 0$} \Comment{Descendant of a micro-tree root}
					\State $e \gets i.E_2 + E_3[i.\size, i.\rep, i.\tau_3]$
					\State \Return{$s +i.A + i.B + i.C_1 + i.C_2 + i.D + e$}
				\Else \Comment{Descendant of a mini-tree root}
					\State $e \gets i.E_1 + i.E_2 + E_3[i.\size, i.\rep, i.\tau_3]$
					\State \Return{$s + i.A + i.B + e$}
				\EndIf
			\ElsIf{$p.\tau_2 \ne 0$} \Comment{Child of a micro-tree root}
				\State \Return{$s + i.A + i.B + i.C_1 + i.C_2 + i.D$}
			\Else \Comment{Child of a mini-tree root}
				\State \Return{$s + i.A + i.B$}
			\EndIf
		\ElsIf{$i.\tau_2 \ne 0$} \Comment{Micro-tree root}
			\State \Return{$s + i.A + i.B + i.C_1 + i.C_2$}
		\Else \Comment{Mini-tree root}
			\State \Return{$s + i.A$}
		\EndIf
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

For the \dfudsSelect{} operation, we reuse the definitions of the pre-order belonging and the first vertex.
We store a compressed array $\dfudsVerticesI{}$, which is similar to the pre-order case; it contains the $\tau_1$ names of all vertices of the tree in DFUDS-order.
\begin{lemma}
	The array $\dfudsVerticesI{}$ contains at most four runs of each $\tau_1$ name.
\end{lemma}
\begin{proof}
	For all vertices $v$ of a mini-tree except for a constant number of exceptions, it holds that the immediately preceding vertex in the array has the same $\tau_1$ name.
	The exceptions are:
	\begin{enumerate}
		\item the mini-tree root; it is the first vertex in DFUDS-order;
		\item the $(\tau_1, 0, 1)$, unless the root was the only child of its parent;
		\item the vertex after the mini-tree dummy vertex; the dummy vertex is canonized and the $\tau_1$ name of the connected mini-tree is used instead;
		\item the vertex after last vertex of the connected mini-tree via a dummy vertex.
	\end{enumerate}
	Each of these vertices start a run, therefore there are at most four runs.
\end{proof}

The space complexity of the compressed array is $o(n)$ bits.
We do the same on the mini-tree level with $\dfudsVerticesII$ which requires $o(B)$ bits.

The operation \dfudsSelect{} is the same \preSelect{}, including the corrections in micro-trees.

\subsubsection{In-Order Numbering}

\begin{lemma}
	We can establish a recursive formula for \inRank{}, which is inspired by \dfudsRank{}:
	\begin{align*}
		\inAnc(i) &= \sum_{a \in \ancestors(i)} \; \sum_{l \in \leftSiblings(a)} (1 + \inSize(l)), \\
		\inRank(i) &= \begin{cases}
			-1 & \textif \degree(i) \le 1; \\
			\inAnc(i) + \inSize(\childFirst(i)) + 1 & \textotherwise.
		\end{cases}
	\end{align*}
	\inSize{} returns the total number of in-order numbers assigned in a subtree of a given vertex.
\end{lemma}
\begin{proof}
	An in-order number is assigned to a vertex which has a degree greater than $1$; we can therefore ignore vertices of degree $0$ or $1$.
	
	We calculate how many in-order numbers have been assigned until vertex $i$ is given its first in-order number.
	The subtrees of left siblings of its ancestors have been fully processed, as has been the subtree of the first child of $i$.
	The $+1$ in \inAnc{} is for in-order numbers already assigned to $\parent(a)$ for its left children (left siblings of $a$).
\end{proof}

The function \inSize{} is implemented the same way as \subtreeSize{} is.
There are precomputed values for mini-tree and micro-tree roots; a look-up table answers queries within a micro-tree.
The only difference is that subtraction of $1$ for a dummy vertex is not needed as leaves are not assigned an in-order number.

We focus on the function \inAnc{} which we again split into several parts for which we store their precomputed value in the min-tree or micro-tree structures.

Let $v_1$ and $v_2$ be ancestors of $i$ such that:
\begin{align*}
	v_1 \in \ancestors(i) &\booland \parent(v_1) = \rootI(i), \\
	v_2 \in \ancestors(i) &\booland \parent(v_2) = \rootII(i).
\end{align*}

We split the precomputed $\inAnc(i)$ into several parts, which are in the most general case:
\begin{alignat}{2}
	\inAnc(i) &= \inAnc(\parent(v_1)) \tag{A}\\
	&\qquad + \inAnc(v_1) &&- \inAnc(\parent(v_1)) \tag{B}\\
	&\qquad + \inAnc(\parent(v_2)) &&- \inAnc(v_1) \tag{C}\\
	&\qquad + \inAnc(v_2) &&- \inAnc(\parent(v_2)) \tag{D}\\
	&\qquad + \inAnc(i) &&- \inAnc(v_2). \tag{E}
\end{alignat}

If $v_1 = v_2$, then $C$ and $D$ do not exist.

When we refer to the mini-tree structure, it is $i.\tau_1$; the micro-tree structure is $(i.\tau_1, i.\tau_2)$.
\begin{description}
	\item[$A$]
	A precomputed value for a mini-tree root; it is stored in a mini-tree structure.
	
	\item[$B$]
	The value $B$ is further split into three parts $B_1 + B_2 + B_3 = B$ such that:
	\begin{align*}
		B_1 &= \sum_{\substack{l \in \leftSiblings(v_1) \\ l.\tau_1 \ne v_1.\tau_1}} (1 + \inSize(l)), \\
		B_2 &= \sum_{\substack{l \in \leftSiblings(v_1) \\ l.\tau_1 = v_1.\tau_1 \\ l.\tau_2 \ne v_1.\tau_2}} (1 + \inSize(l)), \\
		B_3 &= \sum_{\substack{l \in \leftSiblings(v_1) \\ l.\tau_1 = v_1.\tau_1 \\ l.\tau_2 = v_1.\tau_2}} (1 + \inSize(l)).
	\end{align*}
	$B_1$ is stored in the mini-tree structure; $B_2$ is stored in the micro-tree structure.
	If $v_1 = v_2$ then $B_3$ is computed by a look-up table, otherwise it is stored in the micro-tree structure.
	
	\item[$C$]
	The value $C$ is stored in a micro-tree structure.
	
	\item[$D$]
	$D$ is split into two parts $D_2 + D_3 = D$, similar to how $B$ is:
	\begin{align*}
		D_2 &= \sum_{\substack{l \in \leftSiblings(v_2) \\ l.\tau_1 = v_2.\tau_1 \\ l.\tau_2 \ne v_2.\tau_2}} (1 + \inSize(l)), \\
		D_3 &= \sum_{\substack{l \in \leftSiblings(v_2) \\ l.\tau_1 = v_2.\tau_1 \\ l.\tau_2 = v_2.\tau_2}} (1 + \inSize(l)).
	\end{align*}
	$D_2$ is stored in the micro-tree structure, $D_3$ is handled by a look-up table.
	As the micro-tree root is not a mini-tree root, all its right siblings are in the same mini-tree.
	
	\item[$E$]
	It stored in a look-up table.
\end{description}

Note that the \inSize{} of any type (3) connected mini-tree is not accounted in the fields stored in micro-trees, and any type (3) connected micro-tree is not accounted by the look-up table.
They can easily be detected by checking the pre-order number of the dummy vertices, and added later.

\begin{algorithm}
\begin{algorithmic}
\Function{\inRank}{$i$}
	\If{$\degree(i) \le 1$}
		\State \Return{$-1$}
	\Else
		\State $s \gets \inSize(\childFirst(i)) + 1$
		\If{$i.\tau_3 \ne 0$}
			\State $p \gets \parent(i)$
			\If{$p.\tau_3 \ne 0$}
				\State $r \gets \rootII(i)$
				\If{$r.\tau_2 \ne 0$} \Comment{Descendant of a micro-tree root}
					\State $d \gets i.D_2 + D_3[i.\size, i.\rep, i.\tau_3]$%
					\Instr $e \gets E[i.\size, i.\rep, i.\tau_3]$
					\State $s \gets s + i.A + i.B_1 + i.B_2 + i.B_3 + i.C + d + e$
				\Else \Comment{Descendant of a mini-tree root}
					\State $e \gets E[i.\size, i.\rep, i.\tau_3]$
					\State $s \gets s + i.A + i.B_1 + i.B_2 + B_3[i.\size, i.\rep, i.\tau_3] + e$
				\EndIf
			\ElsIf{$p.\tau_2 \ne 0$} \Comment{Child of a micro-tree root}
				\State $d \gets i.D_2 + D_3[i.\size, i.\rep, i.\tau_3]$
				\State $s \gets s + i.A + i.B_1 + i.B_2 + i.B_3 + i.C + d$
			\Else \Comment{Child of a mini-tree root}
				\State $s \gets s + i.A + i.B_1 + i.B_2 + B_3[i.\size, i.\rep, i.\tau_3]$
			\EndIf
			
			\If{$i.\dummyII \ne -1 \booland i.\dummyI \ne i.\tau_2$}
				\If{$\preRank(\bottomII(i)) < \preRank(i)$}
					\State $s \gets s + \inSize(\bottomII(i))$ \Comment{Add it back}
				\EndIf
			\EndIf
		\ElsIf{$i.\tau_2 \ne 0$} \Comment{Micro-tree root}
			\State $s \gets s + i.A + i.B_1 + i.B_2 + i.B_3 + i.C$
		\Else \Comment{Mini-tree root}
			\State $s \gets s + i.A$
		\EndIf
		
		\If{$i.\dummyI \ne -1$}
			\If{$\preRank(\bottomI(i)) < \preRank(i)$}
				\State $s \gets s + \inSize(\bottomI(i))$ \Comment{Add it back}
			\EndIf
		\EndIf
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\bigbreak

The \inSelect{} is similar to \preSelect{}; it has two levels of compressed arrays which we use to navigate to the correct micro-tree.
The array $\inVerticesI$ contains $\tau_1$ names for all vertices of the tree which have been assigned an in-order number in all their instances, therefore a vertex $v$ appears $\degree(v) - 1$ times.

We define more precisely which $\tau_1$ name is stored in the compressed array for each instance of $v$.
If $v$ is a non-root, the $v.\tau_1$ is stored.

If $v$ is a micro-tree root, then we look closer at the mini-trees which contain the children of $v$:
\begin{enumerate}
	\item If $v$ has children, it is a root of several type (1) connected mini-trees; an extreme case is that $v$ is not shared, in which case there is only one such mini-tree.
	The sequences of children of $v$ in these mini-trees are uninterrupted by children in other mini-trees.
	There can be type (2) connected mini-trees, each of them contributing with one child to $v$:
	\begin{enumerate}
		\item before the first type (1) connected mini-tree;
		The name $v.\tau_1$ is reported for all visits of $v$ from a child in such mini-tree.
		
		\item between two type (1) connected mini-trees;
		The name of the preceding type (1) connected mini-tree is reported.
		
		\item after the last type (1) connected mini-tree.
		The name of the preceding type (1) connected mini-tree is reported.
	\end{enumerate}
	For visits of $v$ which result in an in-order number being assigned to $v$ from type (2) connected mini-trees of $v$, we store $v.\tau_1$ in the case (a), and the $\tau_1$ name of the preceding type (1) connected mini-tree in the cases (b) and (c).
	In the cases (a), we also store the number of them in a field $\leftTypeIIi$ in the primary mini-tree; the value is $0$ for non-primary mini-trees.
	
	\item If the mini-tree containing $v$ does not contain any other vertex, then all its children are roots of type (2) connected distinct mini-trees.
	The name $v.\tau_1$ is reported and it is treated as the case (c) in the algorithm.
\end{enumerate}
The name reported for visits from children in a type (1) connected mini-tree $t$ is simply $t$.

\begin{lemma}
	The number of runs in the compressed array $\inVerticesI$ is $O\left(\frac{n}{B}\right)$.
\end{lemma}
\begin{proof}
	There are only the following cases when a vertex $v$ has a different $\tau_1$ name than its immediately preceding vertex $u$ in the array $\inVerticesI$.
	\begin{itemize}
		\item $v$ is the first vertex in its mini-tree which is assigned an in-order number.
		This happens at most once per mini-tree.

		\item $v$ is a parent of a mini-tree dummy vertex which leads to a subtree containing $u$.
		The whole subtree is exhausted before DFS continues with the mini-tree containing $v$, therefore this happens at most once per mini-tree.

		\item $v$ is a root and it was visited from a root of a type (2) connected mini-tree.
		There are at most $O\left(\frac{n}{B}\right)$ type (2) connections, and so are these visits.
		
		\item $v$ is a root and it was visited from the first child in a non-primary type (1) connected mini-tree.
		This happens once per a non-primary mini-tree, whose number is bounded by $O\left(\frac{n}{B}\right)$.
	\end{itemize}
\end{proof}

As the total number of runs is bounded by $O\left(\frac{n}{B}\right)$, the size required to store such array is $o(n)$ bits.

Using the compressed array $\inVerticesI$ we can navigate to the mini-tree which contains the vertex with the in-order number $r$, however it might not be the primary mini-tree.
It can happen that $\tau_1$ was used in $\inVerticesI$ in one of the following cases, which we handle separately before searching for a micro-tree.
\begin{itemize}
	\item If the mini-tree has the only one vertex, we simply return its name.
	We can therefore assume that the mini-tree root has children in the same mini-tree.
	
	\item If the mini-tree is the primary one, then the first $\leftTypeIIi$ occurrences of $\tau_1$ in $\inVerticesI$ are due to type (2) connections.
	From this we know that they refer to the mini-tree root.

	\item If the mini-tree $t$ has $k$ type (b) or (c) children, then the last $k$ occurrences of $t$ in $\inVerticesI$ are due to visits of them.
	If there exists a mini-tree $s > t$ such that it shares its root with $t$, then one extra occurrence is due to visit of $s$.
	All these occurrences correspond to the root being assigned an in-order number.
\end{itemize}

The search continues in a compressed array $\inVerticesII$ which is defined similarly to $\inVerticesI$.
All occurrences are due to in-order numbers which were assigned as the result of returning from and diving into vertices in the mini-tree.
The size of the array is therefore bounded, as is the number of runs; the space complexity is $o(B)$ bits.

Using the compressed arrays $\inVerticesI$ and $\inVerticesII$, we navigate to the correct micro-tree.
We handle the first two special cases in the micro-tree the same we as in the mini-tree.
The last case is handled by comparison with the result of the \inSize{} look-up table; this look-up table comes from the implementation of the \inSize{} function.
The final vertex is then found by a look-up table.

In order to check the bounds of \inSelect{} before it is processed, we use the field $\inSize_1$ which is stored in the root mini-tree and contains the number of all in-order numbers assigned to the vertices of the tree.

\begin{algorithm}
\begin{algorithmic}
\Function{\inSelect}{$r$}
	\State $d_1 \gets \inVerticesI[r - 1]$
	\State $r' \gets \rank(\inVerticesI, r - 1)$
	\If{$|d_1.\microTreeOffsets| = 1 \booland d_1[0].\size = 1 $} \Comment{A single vertex}
		\State \Return{$\rootI(d_1)$}
	\ElsIf{$r' \le d_1.\leftTypeIIi$} \Comment{Left type (2) connections}
		\State \Return{$\rootI(d_1)$}
	\Else
		\State $r' \gets r' - d_1.\leftTypeIIi$
		\If{$r' \ge \size(d_1.\leftTypeIIi)$} \Comment{Right type (2) or type (1) connection}
			\State \Return{$\rootI(d_1)$}
		\Else \Comment{The same for micro-trees}
			\State $d_2 \gets d_1.\inVerticesII[r' - 1]$
			\State $r'' \gets \rank(d_1.\inVerticesI, r' - 1)$
			\If{$d_2.\size = 1$} \Comment{A single vertex micro-tree}
				\State \Return{$\rootII(d_1, d_2)$}
			\ElsIf{$r'' \le d_2.\leftTypeIIii$} \Comment{Left type (2) connections}
				\State \Return{$\rootII(d_1, d_2)$}
			\Else
				\State $r'' \gets r'' - d_2.\leftTypeIIii$
				\If{$r'' \ge \inSize[d_2.\size, d_2.\rep, 0]$} \Comment{Right (2) or right (1)}
					\State \Return{$\rootII(d_1, d_2)$}
				\Else
					\State \Return{$\canonize(d_1, d_2, \inSelect[d_2.\size, d_2.\rep, r''])$}
				\EndIf
			\EndIf
		\EndIf
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Leaf Operations}

All the \leafAny{} operations are analogies of operations which we have shown before.
The global \leafRank{} and \leafSelect{} operations are similar to \preRank{} and \preSelect{}.
We extend them to be parametrized by the root of a subtree to which they are restricted.

We support the parametrized operations \leafSize{} the same way we support \subtreeSize{}, and \leafFirst{} which returns the first leaf in the subtree of a given vertex the same way as \deepestVertex{}.

We can then restrict the leaf operations to a subtree:
\begin{algorithm}
\begin{algorithmic}
\Function{\leafRank}{$a, i$}
	\State \Return{$\leafRank(i) - \leafRank(\leafFirst(a)) + 1$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\Function{\leafSelect}{$a, i$}
	\State \Return{$\leafSelect(i + \leafRank(\leafFirst(a)) - 1)$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsection{Ancestral Operations}

We define a tree $T_1$ whose nodes are roots of primary mini-trees.
A node $u$ is a parent of node $v$ if $v.\parent_1 = u$.
The tree $T_1$ has $O\left(\frac{n}{B}\right)$ nodes.

Similarly we define a tree $T_2$ for each mini-tree $t$ which consists of nodes corresponding to primary micro-tree roots within the mini-tree $t$.
A node $u$ is a parent of node $v$ in $T_2$ if $v.\parent_1 = u$.
This tree $T_1$ has $O\left(\frac{B}{b}\right)$ nodes.

\subsubsection{Lowest Common Ancestor}

The operation \lca{} will be solved on three levels: micro-tree, mini-tree and the whole tree.
If $i_1$ and $i_2$ are within the same micro-tree we use a look-up table.
Otherwise we use an LCA structure which uses the techniques from lemma \ref{lemma:rmq2}.

\begin{lemma}\label{l:ff-lca}
	We can solve the LCA operation on the trees $T_1$ and $T_2$ using indices of $o(n)$ and $o(B)$ bits.
\end{lemma}
\begin{proof}
	We first assume a general tree $T$ with $p$ nodes.
	We define an array $E$ which contains nodes as they are visited during an Eulerian tour starting in the root.
	The array $E$ contains $2p - 1$ nodes, which corresponds to every vertex being visited from each of its neighbors plus one for the root where the tour starts and ends.
	The answer to $\lca(u, v)$ is the shallowest node between the first occurrence of $u$ and the first occurrence of $v$ in the array $E$.
	We can therefore reduce the task of finding the lowest common ancestor to task of finding the minimum value in the given range in an array $D[i] = \dep(E[i])$.
	The position of the minimum can be found by a range minimum query using a precomputed (not look-up) table as in lemma \ref{lemma:rmq2}.
	
	In each node of the tree, we store its depth and the index of its the first occurrence in the array $E$, which we do not store anywhere.
	The precomputed table contains directly names of the nodes; it requires requires $p \log^2 p$ bits.
	In the case of two overlapping intervals we simply compare the depths of the two candidates.
	
	In case of $T_1$, we use the field $\depthI$ since the relation of one node being an ancestor of the other is preserved.
	The name of the node is its $\primaryI$ name.
	The tree $T_1$ has $O\left(\frac{n}{B}\right)$ nodes, so the space required is $O\left(\frac{n}{B} \log^2 n\right) = o(n)$ bits for $c \ge 3$.
	($c$ is the constant from definition of the size $B$.)
	
	In case of $T_2$, we use $\depthII$ for determining the depth and $\primaryII$ as the name of a node.
	The tree $T_2$ has $O\left(\frac{B}{b}\right)$ nodes, which results in space $O\left(\frac{B}{b} \log^2 B\right) = o(B)$ bits.
\end{proof}

If the vertices are in the same mini-tree, we solve it by querying $T_2$ for the lowest common ancestor using the lemma \ref{l:ff-lca} (function \lcaI); in case when they are in different mini-trees, we query the tree $T_1$ (function \lcaII).

There are two special cases which need to be addressed in the algorithm.
\begin{enumerate}
	\item If the vertices $i_1$ and $i_2$ are in mini-trees or micro-trees which share their root, the answer is the root.
	
	\item If the vertices are in unaffiliated mini-trees, the reduction to LCA of their roots might not be correct if the answer was the root of $i_1$, without loss of generality.
	We need to check if the path between the vertices $i_1$, $i_2$ uses the mini-tree dummy vertex in the mini-tree of $i_1$, which we test by the operation $\isAncestor{}$.
	In such case, we replace $i_2$ by the dummy vertex and proceed as before.
	
	The same applies for reduction to roots of micro-trees.
	However, we are only interested in micro-tree dummy vertices.
\end{enumerate}

\begin{algorithm}
\begin{algorithmic}
\Function{\lca}{$i_1, i_2$}
	\If{$i_1.\tau_1 = i_2.\tau_1$} \Comment{The same mini-tree}
		\If{$i_1.\tau_2 = i_2.\tau_2$} \Comment{The same micro-tree}
			\State \Return{$\canonize(i_1.\tau_1, i_1.\tau_2, \lca[i_1.\size, i_1.\rep, i_1.\tau_3, i_2.\tau_3])$}
		\ElsIf{$i_1.\primaryII = i_2.\primaryII$} \Comment{Type (1) connected micro-trees}
			\State \Return{$\rootII(i_1)$} \Comment{Micro-tree root}
		\Else \Comment{Unaffiliated micro-trees}
			\If{$i_1.\dummyII \ne -1 \booland i_1.\tau_2 \ne i_1.\dummyI$}
				\If{$\isAncestor(\bottomII(i_1), i_2)$} \Comment{Test type (3) connection}
					\State \Return{$\lca(i_1, \dummyII(i_1))$} \Comment{Use $d$ instead of $i_2$}
				\EndIf
			\EndIf
			\If{$i_2.\dummyII \ne -1 \booland i_2.\tau_2 \ne i_2.\dummyI$}  \Comment{Symmetrical}
				\If{$\isAncestor(\bottomII(i_2), i_1)$}
					\State \Return{$\lca(i_2, \dummyII(i_2))$}
				\EndIf
			\EndIf
			\State \Return{$\rootII(i_1.\tau_1, \lca_2(i_1.\tau_1, i_1.\primaryII, i_2.\primaryII))$}
		\EndIf
	\ElsIf{$i_1.\primaryI = i_2.\primaryI$} \Comment{Type (1) connected micro-trees}
		\State \Return{$\rootI(i_1)$} \Comment{Mini-tree root}
	\Else \Comment{Unaffiliated mini-trees}
		\If{$i_1.\dummyI \ne -1$}
			\If{$\isAncestor(\bottomI(i_1), i_2)$} \Comment{Test type (3) connection}
				\State \Return{$\lca(i_1, \dummyI(i_1))$} \Comment{Use $d$ instead of $i_2$}
			\EndIf
		\EndIf
		\If{$i_2.\dummyII \ne -1$} \Comment{Symmetrical}
			\If{$\isAncestor(\bottomI(i_2), i_1)$}
				\State \Return{$\lca(i_2, \dummyI(i_2))$}
			\EndIf
		\EndIf
		\State \Return{$\rootI(\lca_1(i_1.\primaryI, i_2.\primaryI))$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Level Ancestor}

If the desired vertex $j \in \ancestors(i) \booland \dep(j) = \dep(i) - d$ is not contained in the current mini-tree, we use the tree $T_1$ to find the correct mini-tree.
We follow the same way for micro-trees, and finally find the vertex $j$ using a look-up table in the correct micro-tree.

When we search the tree $T_1$, we not only want to know the name of the mini-tree $t$ which contains $j$, but also the the lowest ancestor $j'$ in it.
The lowest ancestor $j'$ in a mini-tree $t$ can be:
\begin{enuminline}
	\item its root if $i$ is in a subtree of a type (2) connected mini-tree;
	\item parent of its dummy vertex if $i$ is a subtree of a type (3) connected mini-tree.
\end{enuminline}
Since each mini-tree has at most one mini-tree dummy vertex, it is easy to check which option occurs in constant time.

We use the same technique as for \lrmSearch{} in section \ref{ff-search} to find the correct mini-tree.
Each node $i$ has already been assigned its minimum depth in field $\depthI$.
We first use a tiny compressed array $J_i$ and then a collection of compressed arrays $L$.

The same structure is built for the tree $T_2$ where the depths are $\depthII$.
We call the search functions \ancSearchI and \ancSearchII.

\begin{algorithm}
\begin{algorithmic}
\Function{\levelAncestor}{$i, d$}
	\State $v \gets \dep(i) - d$
	\If{$v < 0$}
		\State \Return{$-1$}
	\EndIf
	\If{$v < \dep(\rootI(i))$} \Comment{Wrong mini-tree}
		\State $t \gets \ancSearchI(\rootI(i), v)$
		\If{$\isAncestor(\bottomI(t), i)$} \Comment{Type (3) connection}
			\State $i \gets \parent(\dummyI(t))$
		\Else \Comment{Type (2) connection}
			\State $i \gets \rootI(t)$
		\EndIf
	\EndIf
	\If{$v < \dep(\rootII(i))$} \Comment{Wrong micro-tree}
		\State $t \gets \ancSearchII(i.\tau_1, \rootII(i), v)$
		\If{$\isAncestor(\bottomII(t), i)$} \Comment{Type (3) connection}
			\State $i \gets \parent(\dummyII(t))$
		\Else \Comment{Type (2) connection}
			\State $i \gets \rootII(t)$
		\EndIf
	\EndIf
	\State \Return{$\canonize(i.\tau_1, i.\tau_2, \levelAncestor[i.\size, i.\rep, i.\tau_3, \dep(i) - v])$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsection{Level Operations}

\subsubsection{Level First}

We first show how to support the operation \levelFirst{} which is restricted to the subtree of a vertex $i$.
The operation \levelLast{} is analogous, and we address the differences at the end.

For each mini-tree root $i$ we define an array $\lfirstI$:
$$ i.\lfirstI[j] = \argmin_{\substack{\preRank(v) \ge \preRank(i) \\ \dep(v) = \dep(i) + j}} \preRank(v). $$
This array contains \emph{level-first descendants} of $i$ for $j \le \hei(i)$ as it has the correct depth and it is the first one such.

We cannot afford to store the arrays $\lfirstI$, however we observe the following fact:
If for two mini-tree roots $i$, $j$ and level $d$ holds:
$$i.\lfirstI[d - \dep(i)] = j.\lfirstI[d - \dep(j)], $$
then for $k \ge 0$ holds that:
$$i.\lfirstI[d - \dep(i) + k] = j.\lfirstI[d - \dep(j) + k].$$
This is basically the same property which holds for the arrays $\lrm_i$ in section \ref{ff-search}.
Before we use it, we formulate and prove the following lemma.

\begin{lemma}\label{l:level-first-3}
	There are at most three runs for each $\tau_1$ name in the array $\lfirstI$.
\end{lemma}
\begin{proof}
	Let's assume that the root $v$ of a mini-tree $t$ is a level-first descendant of $i$, then $v.\tau_1$ is in the array.
	We also assume that $v$ has children in the same mini-tree.
	There are two possibilities how a run of level-first descendants can be interrupted:
	\begin{enumerate}
		\item We look at the first child of $v$.
		If it is not in the same mini-tree, then $v$ must have some type (2) connected mini-trees $L$ to the left.
		If $h = \max_{l \in L} \hei(l)$ is less than the height of $t$ (restricted to $t$), then the $v.\tau_1$ will appear in the array once all subtrees of $L$ end.
		
		\item If a level-first descendant of $v$ is a mini-tree dummy vertex, then the level-first descendants of its mini-tree $s$ will be in the array.
		If the $h = \dep(s) - dep(v) + \hei(s)$ is less than the height of the mini-tree $t$ (restricted to $t$), then the $v.\tau_1$ will appear in the array once the subtree of $s$ ends.
	\end{enumerate}
	These two causes of interruption can overlap, however they can cause at most three runs of $v.\tau_1$.
	
	If the root was not the level-first descendant but another vertex of the mini-tree $t$ occurs in the array, we can apply the same reasoning about the second type of interruption.
	That proves that such $\tau_1$ can appear in at most two runs.
\end{proof}

\bigbreak

We build a tree $T_1$ as a trie from the reversed arrays $\lfirstI$ with an additional artificial root.
We compress the tree by contracting paths between nodes which are either:
\begin{enumerate}
	\item The artificial root node.
	\item Nodes corresponding to mini-tree roots.
	All leaves of $T_1$ are mini-tree roots, however not all mini-tree roots are leaves in $T_1$.
	\item Branching nodes in the tree $T_1$.
	Their number is bounded by the number of leaves of $T_1$.
	\item Nodes corresponding to vertices in the arrays $\lfirstI$ such that their predecessor has a different $\tau_1$ name.
\end{enumerate}
Not counting branching nodes, there are at most three vertices for each mini-tree, which follows from the previous lemma.
The number of nodes in the compressed tree is $O\left(\frac{n}{B}\right)$.

We associate each node $n$ with the depth of the vertex which it represents in the original tree.
We store the information about the nodes in an array; each node knows its $\tau_1$ name, its depth, and its pre-order number $k$ in $T_1$.
We also store the pre-order number $k$ of the node which corresponds with the mini-tree root as a field $\lfirstKI$ in a mini-tree structure.

Since this tree has increasing values on paths from leaves to the root, we use the same structures as for $T_{\LRM}$ in section \ref{ff-search}.
\begin{itemize}
	\item A tiny compressed array $J_n$ for each node $n$.
	The $J$ contains pre-order numbers $k$ of the nodes at distances which are powers of two.
	Contrary to the definition in section \ref{ff-search}, we use the operation \pred{} for definition of the compressed array.
	\item A collection of compressed arrays $L$ storing all ladders.
	Similarly to $J$, the operation \pred{} is used.
	\item An array $\ladder$ which contains information about to which ladder each node belongs.
\end{itemize}
These structures take $O\left(\frac{n}{B} \log^2 n\right) = o(n)$ bits for $c \ge 3$.

We use the algorithm \LRMSearch{} which returns the first ancestor node $j$ in the tree $T_1$ such that $\dep(j)$ less than or equal to the desired one.
In our case, the function returns the $\tau_1$ name of the node.
Note that in a general case, we should check whether the node which we found is a descendant of the queried node, which can be done by \isAncestor{}.
However, in the algorithm as we formulate it, we check the bounds beforehand, so it is not necessary.
This concludes the search for the correct mini-tree.

We build a similar structure for querying level-first descendants of micro-tree roots for each mini-tree.
The searches are processed by functions \ldSearchI{} and \ldSearchII{}.
Finally, we use a look-up table to find the answer within the correct micro-tree.

The algorithm tests two alternatives and chooses the one with smaller pre-order number.
\begin{enumerate}
	\item If the query starts with a mini-tree root, the correct mini-tree is found, then the correct micro-tree is found, and finally the correct vertex is found.
	\item If the query starts with a micro-tree root, a micro-tree is found within a potentially incorrect mini-tree, then a vertex is found.
	The mini-tree dummy vertex is check, as it could contain the correct answer; a recursive call causes triggers the option (1).
	\item If the query starts with a non-root, a vertex is found in a look-up table.
	The dummy vertex in the micro-tree is checks; a recursive call leads to options (1) or (2).
\end{enumerate}
The algorithm uses recursion of a constant depth.


\begin{algorithm}
\begin{algorithmic}
\Function{\levelFirst}{$i, d$}
	\If{$d < \dep(i) \booland d > \dep(i) + \hei(i)$}
		\State \Return{$-1$} \Comment{Answer does not exist}
	\EndIf
	
	\State $c \gets -1$ \Comment{Alternative candidate}

	\If{$i.\tau_2 = 0 \booland i.\tau_3 = 0$} \Comment{Mini-tree root}
		\State $i \gets \rootI(\ldSearchI(i.\lfirstKI, d))$ \Comment{Find mini-tree (root)}
	\EndIf
	
	\If{$i.\tau_3 = 0$} \Comment{Micro-tree root}
		\If{$i.\tau_2 \ne 0 \booland i.\tau_3 = 0 \booland i.\dummyAncestor$}
			\State $c \gets \levelFirst(\bottomI(i))$ \Comment{Check mini-tree dummy vertex}
		\EndIf
		\State $i \gets \rootII(i.\tau_1, \ldSearchII(i.\tau_1, i.\lfirstKII, d))$ \Comment{Find micro-tree (root)}
	\EndIf

	\If{$i.\tau_3 \ne 0 \booland \isAncestor[i.\size, i.\rep, i.\tau_3, i.\dummyII]$}
		\State $c \gets \levelFirst(\bottomII(i))$ \Comment{Check dummy vertex}
	\EndIf
	\State $i \gets \levelFirst[i.\size, i.\rep, i.\tau_3, d - \dep(i)]$ \Comment{Find vertex}
	
	\State \Return{$\textif c \ne -1 \booland \preRank(c) < \preRank(i) \textthen c \textelse i$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Level Last}

The operation \levelLast{} differs from \levelFirst{} in minor details:
\begin{itemize}
	\item We define an arrays $\llastI$ (and $\llastII$):
	$$ i.\llastI[j] = \argmax_{\substack{\preRank(v) \le \preRank(i) + \subtreeSize(i) - 1  \\ \dep(v) = \dep(i) + j}} \preRank(v) $$
	\item There is one more cause of interruption in the \levelLast{} version of the lemma \ref{l:level-first-3}.
	Type (1) connected mini-trees pose the same reason for interruption as the type (2) connections.
	This is because the canonical names are reported.
	\item We select the candidate with highest rank at the last line of the algorithm.
\end{itemize}

\subsubsection{Level Next and Level Previous}

We focus on \levelNext{}; the operation \levelPrev{} is symmetrical.

We distinguish four cases:
\begin{enumerate}
	\item the vertex $i$ is the level-last vertex in the subtree of $a$.
	Then there is no next vertex on the level.
	
	\item the vertex $i$ is not the level-last vertex in its micro-tree.
	We use a look-up table to handle this case.
	We also need to check for type (3) connected subtree which could contain the answer.
	This check can be easily done by comparing pre-order rank of $i$ and $\dummyII(i)$.
	
	\item the vertex $i$ is the level-last vertex in its micro-tree, then we search the micro-tree $t_2$ which is ``to the right'' from $i$.
	We find its $\tau_2$ name using a structure which we describe later.
	We distinguish two cases:
	\begin{itemize}
		\item If the micro-tree $t_2$ contains a dummy vertex and $i$ is in its subtree, then we solve the search in $t_2$ using a look-up table \levelNext' searching for the first vertex $v$ on the desired level with $\preRank(v) > \preRank(\bottomII(t_2))$.
		\item Otherwise, it is the level-first vertex in the micro-tree $t$.
	\end{itemize}

	\item The vertex $i$ is the level-last vertex in its mini-tree.
	We need to find vertex in the mini-tree $t_1$ which is ``to the right'' from the current one.
	As before, we distinguish two cases:
	\begin{itemize}
		\item If $i$ is a descendant of the dummy vertex in $t_1$, then we need to find the micro-tree which contains the vertex $v$ such that $\preRank(v) > \preRank(\bottomI(t_1))$.
		
		As there is at most one dummy vertex in a mini-tree, we store a compressed array $\dummyNext$ which contains $\tau_2$ names of micro-trees which contain the answer for all admissible levels.
		This compressed array contains at most $B$ elements in $O\left(\frac{B}{b}\right)$ runs and therefore uses $O\left(\frac{B}{b} \log B\right) = o(B)$ bits of space.
		The number of runs follows from the constant bound in lemma \ref{l:level-first-3} and the fact that there are $O(\frac{B}{b})$ micro-trees in a mini-tree.

		Let $t_2$ be the micro-tree which is obtained from the compressed array $\dummyNext$.
		We finish the query as in the previous case since $\dummyII(t_2)$ could be an ancestor of $i$.
		
		\item Otherwise, the answer is the level-first vertex in the mini-tree $t_1$.
	\end{itemize}
\end{enumerate}

We define a graph $G$ whose nodes are mini-trees and each two nodes $x, y$ are connected whenever there is a vertex $u$ in $x$ and a vertex $v$ in $y$ such that $\levelNext(i, u) = v$.

\begin{lemma}\label{l:level-graph}
	The graph $G$ has $O\left(\frac{n}{B}\right)$ edges.
\end{lemma}
\begin{proof}
	The graph is planar, therefore there is a linear bound on number of edges.
\end{proof}

For each mini-tree $i$, we define an array $\lnextI$:
$$ \lnextI[j] = \levelNext(\rootI(0), \levelLast(i, \dep(i) + j)).\tau_1$$
If there is no next vertex, than we use the name $-1$.

We build a collection of compressed arrays out of all $\lnextI$ arrays, which will be stored in the global structure.
They contain $O(n)$ elements in total as each vertex except for mini-tree roots is the rightmost one in at most one mini-tree, and the number of mini-tree roots is $O\left(\frac{n}{B}\right)$.
There are at most $O\left(\frac{n}{B}\right)$ runs in all arrays, which follows from the lemmas \ref{l:level-graph} and \ref{l:level-first-3}; there are only $O(1)$ ways how three and three runs can be combined together.
The extra ``no next vertex'' names do not matter as we they form a single run until the end of the array.
The collection of compressed arrays requires $O\left(\frac{n}{B} \log n\right) = o(n)$ bits of space.

We construct a similar structure $\lnextII$ for all micro-trees, storing the $\tau_2$ name of the micro-trees containing the level-next vertex.
This requires $O\left(\frac{B}{b} \log B\right) = o(B)$ bits of memory, and it is stored in each mini-tree structure.

\begin{algorithm}
\begin{algorithmic}
\Function{level\_next}{$a, i$}
	\If{$i = \levelLast(a, \dep(i))$}
		\State \Return{$-1$}
	\EndIf
	
	\State $j \gets \levelNext[i.\size, i.\rep, i.\tau_3]$ \Comment{Search in micro-tree}
	\If{$i.\dummyII \ne -1 \booland (j = -1 \boolor \preRank(\bottomII(i)) < \preRank(j))$}
		\State $f \gets \levelFirst(\bottomII(i), \dep(i))$  \Comment{Check dummy vertex}
		\If{$f \ne -1$}
			\State \Return{$f$}
		\EndIf
	\ElsIf{$j \ne -1$}
		\State \Return{$i.\tau_1, i.\tau_2, j$} \Comment{Answer in micro-tree}
	\EndIf
	
	\State $t_2 \gets i.\lnextII[i.\tau_2, \dep(i) - \dep(\rootII(i))]$ \Comment{Search for micro-tree}
	\If{$t_2 \ne -1 \booland t_2.\dummyII \ne -1 \booland \isAncestor(\bottomII(t_2), i)$}
		\State \Return {$\levelNext'[t_2.\size, t_2.\rep, \dep(i) - \dep(\rootII(t_2))]$}
	\ElsIf{$t_2 \ne -1$}
		\State \Return{$\levelFirst(t_2, \dep(i))$}
	\EndIf
	
	\State $t_1 \gets \lnextI[i.\tau_1, \dep(i) - \dep(\rootII(i))]$ \Comment{Search for mini-tree}
	\If{$t_1 \ne -1 \booland t_1.\dummyI \ne -1 \booland \isAncestor(\bottomI(t_1), i)$}
		\State $t_2 \gets t_1.\dummyNext[\dep(i) - \dep(\dummyI(t_1))]$
		\If{$t_2.\dummyII \ne -1 \booland \isAncestor(\bottomII(t_2), i)$}
			\State \Return {$\levelNext'[t_2.\size, t_2.\rep, \dep(i) - \dep(\rootII(t_2))]$}
		\Else
			\State \Return{$\levelFirst(t_2, \dep(i))$}
		\EndIf
	\ElsIf{$t_1 \ne -1$}
		\State \Return{$\levelFirst(t_1, \dep(i))$}
	\Else
		\State \Return{$-1$}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsection{Final Thoughts}

In the beginning we defined the size $B$ dependent on the constant $c \ge 2$.
We can set $c = 2$ as long as we do not require the ancestral and level operations in the form we have shown (they require $c \ge 3$).
However, it is not true that $c > 2$ is required as \cite{farzan2014uniform} shown the same structure with slightly more complicated operations for which $c = 2$ is sufficient.
We chose the simpler options as they allowed us to reuse structures which we defined in other parts of this work.

The TC data structure supports all operations of FF; it is better in ranking operations (\postRank{}, \postSelect{}, \dfudsRank{}, \dfudsSelect{}) which are not supported by the former one.
The advantage of TC is that it is easier to extend it by adding small bits to an existing skeleton.
On the other hand, some operations are significantly harder to implement.

\section{Universal Succinct Representation}

All of the previous structures can be split into two parts (recalling the definition of systematic data structures):
\begin{description}
	\item[data]
	In case of BP (and FF -- the same representation with different indices) and DFUDS, it is clearly the bit string $S$ of size $2n$ bits.

	In case of TC, it is the representations of micro-trees in form of a sequence of pairs $(\size, \rep)$.
	Although it is not enough to restore the original tree -- for that we would need to store at least the number of mini-trees in the tree, number of micro-trees in a mini-tree, parents, primaries and dummy vertices, we do not consider it here.
	
	\item[index] 
	Any structure or structures of size $o(n)$ bits which speed up the queries; for BP and DFUDS they were indices for \rank{}, \select{}, \match{}, \rmqi{}.
	In case of TC, the global, mini-tree and micro-tree structures without what we defined as \emph{data} take only $o(n)$ bits and will be considered as an index.
\end{description}

Any algorithm for word-RAM can access only $w = \Theta(\log n)$ consecutive bits of memory in one step.
Since all the operations which we have shown were formulated for word-RAM, at each step at most $w$ bits of the bit string $S$ or at most one micro-tree representation $(\size, \rep)$ can be accessed in the memory.
We can replace the data part of each data structure by simulation of the memory access in time $O(1)$.
As long as the structure providing the simulation uses only $2n + o(n)$ bits, the original data structure is still succinct.

We show a data structure for a universal succinct representation of trees which was described by \cite{farzan2009universal}.

The data structure provides the following three operations in running time $O(1)$:
\begin{description}
	\item[$\bpSubstring(i, s) \rightarrow S$]
	It returns $s \le w$ bits of BP representation staring at position $i$.
	
	\item[$\dfudsSubstring(i, s) \rightarrow S$] 
	It returns $s \le w$ bits of DFUDS representation staring at position $i$.
	
	\item[$\tcMicrotree(\tau_1, \tau_2) \rightarrow (\size, \rep)$]
	Returns the micro-tree representation by its $(\tau_1, \tau_2)$ name.
	We assume that the decomposition and the naming schema which we described in the section \ref{s:TC} is used.
\end{description}

Although the parameter $s$ can be in range $[1, w]$, we will restrict it to a fraction of $\log n$; the exact value depends on the target representation and on a constant which we leave as a parameter of the data structure.
We also constrain $i$ to be a multiple of $s$.
The answer to a query with unrestricted $i$ and $s$ can still be obtained by $O(1)$ queries of the restricted type.

\bigbreak

Assuming that such data structure exists, we can equip it with all \emph{indices} (for BP, DFUDS and TC) in order to obtain a succinct data structure which supports the union of all operations of individual representations.
Although it may seem that TC is superior to any other representation, there are still advantages:
\begin{itemize}
	\item If there are more ways to support the same operation, the fastest one or the one requiring the smallest index (both in terms of a real implementation) can be chosen.
	\item If any new operation becomes supported by either of the representations, the universal data structure can benefit from it.
\end{itemize}

\subsection{Restriction to Mini-Trees}

We start with the same two-level decomposition as in the Tree Covering representation.
The mini-trees are the primary part of the data structure, which is where the operations \bpSubstring{} and \dfudsSubstring{} are supported.
The micro-trees will be used much later since they are required only to support the operation \tcMicrotree{}.

Almost every parenthesis in the bit strings $S$ of BP and DFUDS representation can be associated with a vertex:
\begin{itemize}
	\item an opening parenthesis in BP directly represents a vertex;
	\item a closing parenthesis in BP represents the same vertex as the matching opening one;
	\item the first parenthesis in DFUDS is unassociated;
	\item the first parenthesis following a closing one or parenthesis at position $1$ directly represents a vertex;
	\item any other parenthesis in DFUDS represents the same vertex as the preceding one.
\end{itemize}
Contrary to the original proposal in \cite{farzan2009universal}, we use a different association in the DFUDS representation.
The advantage of our approach is that the algorithms become simpler and we are able to generate bigger blocks of bits.

We define two compressed arrays $\bp$ and $\dfuds$ which contain the $\tau_1$ name in the TC representation of the vertex associated with the parenthesis at every position.

\begin{lemma}\label{l:usr-runs}
	Every $\tau_1$ name occurs in at most 4 runs in the compressed array $\bp$ and 3 runs in $\dfuds$.
\end{lemma}
\begin{proof}
	The definitions of the BP and DFUDS representations are based on pre-order traversal of the tree, and they can be expressed recursively.
	All vertices between the first and the last occurrence of the $\tau_1$ name of a mini-tree $t$ are in the subtree of the mini-tree root $v$ of $t$.
	We call \emph{own} the children of $v$ which are contained in the mini-tree $t$.
	
	There are three types of connections which connect other mini-trees to $t$.
	All type (1) and type (2) connections involve the root $v$; some subtrees rooted in children of $v$ can belong to other mini-trees.
	The own children of $v$ form an interval which is not interrupted by any type (1) nor type (2) connection.
	
	In the array $\bp$, the subtree of $v$ consists of:
	\begin{enumerate}
		\item the opening parenthesis of the root $v$,
		\item subtrees of children preceding own children (the first interruption),
		\item subtrees of own children,
		\item subtrees of children following own children (the second interruption),
		\item the closing parenthesis of the root $v$.
	\end{enumerate}
	
	In the array $\dfuds$, the subtree of $v$ is slightly different:
	\begin{enumerate}
		\item the degree sequence of the root $v$,
		\item subtrees of children preceding own children (the only interruption),
		\item subtrees of own children,
		\item subtrees of children following own children.
	\end{enumerate}
	
	Any of the parts in both arrays can be empty, which can only decrease the number of interruptions.
	Each mini-tree can further have up to one type (3) connection which can interrupt once the run containing own children.
	
	The number of runs follows from the number of interruptions.
\end{proof}

According to the lemma, there are at most $O(1)$ runs of each name, therefore the size of the compressed arrays $\bp$ and $\dfuds$ is $o(n)$.

\bigbreak

We immediately solve all queries which span over multiple $\tau_1$ names in the arrays $\bp$ and $\dfuds$, and also all queries which involve any bit of the representation of any mini-tree root in the DFUDS case.

For each run, we store the last and the following $w$ bits of both representations.
In case of DFUDS and a primary mini-tree, we also store the first $w$ bits starting at the position of the closing parenthesis in the degree sequence of the root.
This requires $O\left(\frac{n}{B} w\right) = o(n)$ bits.

We can detect such queries in $O(1)$ time by the following two conditions:
\begin{gather*}
	\runLast(i) - i < b, \\
	\dfuds[i].\primaryI = \dfuds[i] \booland \rank(\dfuds, i) \le \dfuds[i].\degree + 1.
\end{gather*}
In the first case we simply answer the query using the parts which we have stored; the number of the run can be found using the function \elementIndex{}.
In case of the root in DFUDS representation, we first generate the right number of opening parentheses and then append the stored part.
All this can be implemented using arithmetic and bitwise operations on word-RAM.

From now on, we can assume that all queries span a single run.
They can therefore be restricted to a query on the BP or DFUDS representation of a single mini-tree.

We do not have to handle specially the case of existence of a mini-tree dummy vertex since its encounter causes an interruption in the arrays $\bp$ and $\dfuds$, and therefore such query must have already been solved.
It is still necessary to keep it in order to calculate the degree of its parent correctly in the DFUDS representation.

We store the offset of the dummy vertex in the BP and DFUDS representation of the mini-tree.
The dummy vertex is represented by the sequence \str{()} in BP and by \str{)} in DFUDS representation.
The position $i$ is transformed to a position~$i'$ inside the BP and DFUDS representations of the mini-tree.

\begin{algorithm}
\begin{algorithmic}
\Function{\bpReduce}{$i$}
	\State $i' \gets \rank(\bp, i) - 1$
	\If{$\bp[i].\tau_1 \ne \bp[i].\primaryI$} \Comment{Not primary}
		\State $i' \gets i' + 1$ \Comment{Reintroduce the root}
	\EndIf
	\If{$\bpDummy \ne -1 \booland i' \ge \bpDummy$} \Comment{Dummy vertex is before}
		\State $i' \gets i' + 2$ \Comment{Introduce the dummy vertex}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\Function{\dfudsReduce}{$i$}
	\State $i' \gets \rank(\dfuds, i) - 1$
	\If{$\dfuds[i].\tau_1 = \dfuds[i].\primaryI$} \Comment{Primary}
		\State $i' \gets i' - \dfuds[i].\degree - 1$ \Comment{Remove root's degree sequence}
	\EndIf
	\State $i' \gets i' + \dfuds[i].\degreeOwn + 1$ \Comment{Reintroduce the root}
	\If{$\dfudsDummy \ne -1 \booland i' \ge \dfudsDummy$} \Comment{Dummy vertex is before}
		\State $i' \gets i' + 1$ \Comment{Introduce the dummy vertex}
	\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

So far we needed the following fields to be stored:
\begin{description}
	\item[Global]
	\begin{description}
		\item[]
		
		\item[$\bp$]
		The compressed array which maps positions of parentheses of the BP representation to mini-trees.
		
		\item[$\dfuds$]
		The compressed array which maps positions of parentheses of the DFUDS representation to mini-trees.
		
		\item[$\bpLast, \bpFollowing, \dfudsLast, \dfudsFollowing$]
		Arrays containing words of the last and the following $w$ bits for each run and for both representations.
	\end{description}
	
	\item[Mini-tree]
	\begin{description}
		\item[]
		
		\item[$\tau_1, \primaryI$]
		They are the same as in the TC data structure.
		
		\item[$\degree, \degreeOwn$]
		The full degree of the mini-tree root, and its root when restricted to children in this mini-tree. 
		
		\item[$\bpDummy, \dfudsDummy$]
		Positions of the dummy vertex in the BP and DFUDS representations of the mini-tree.
		
		\item[$\dfudsStart$]
		Contains the $w$ bits of the DFUDS representation starting at the position of the closing parenthesis in the degree sequence of the root.
	\end{description}
\end{description}

\bigbreak

From now on, we restrict our description to a single mini-tree; we ignore all other mini-trees, including those connected via the dummy vertex.

We call a vertex \emph{significant} if its subtree size is larger than $d' = \frac{\log n}{d}$, for a constant $d$.
A \emph{skeleton} of a mini-tree is the subtree induced by significant vertices.
The skeleton must be connected since each ancestor of a significant vertex is also significant.

There are at most $O\left(\frac{B}{\log n}\right)$ leaves in the skeleton as the subtree of each of them contains at least $d'$ vertices.
We can assume that there is also at least one significant vertex as otherwise the size of the representation of the mini-tree is less than $w$, and so every query has already been solved.

\subsection{Skinny Mini-Trees}

We call a mini-tree \emph{skinny} if its skeleton is a path.
We solve this special case first, and then generalize it to all skeletons.

We use the same notation as the authors in \cite{farzan2009universal}:
Let $P$ by the skeleton, which is a path, $u$ its leaf and $v$ the last child of $u$.
Let us define the following sets:
\begin{align*}
	S &= \{ s : \parent(s) \in P \booland s \notin P \} \\
	S_D &= \{ s \in S : \preRank(s) \le \preRank(v) \} \\
	S_U &= \{ s \in S : \preRank(s) > \preRank(v) \}
\end{align*}

We represent a skinny mini-tree by four bit strings:
\begin{description}
	\item[Path down, $P_D$]
	The concatenation of the unary degree sequences of vertices in the skeleton, assuming only their children in $S_D$.
	They are stored in the order from the root to the leaf $u$.
	
	\item[Path up, $P_U$]
	The same for children in $S_U$ and direction from $u$ to the root.
	
	\item[Trees on path down, $T_D$]
	Subtrees of $S_D$ stored consecutively according to their pre-order numbers.
	We call the trees \emph{left dangling trees}.
	The trees can be stored in any self-delimiting representation which requires at most $2k - 1$ bits for a tree with $k$ vertices.
	We can either use BP without the first parenthesis, which is an opening one, or DFUDS without the artificially prepended opening parenthesis.
	
	\item[Trees on path up, $T_U$]
	The same for subtrees of vertices $S_U$ ordered by their pre-order numbers.
	We call them \emph{right dangling trees}.
\end{description}

These four bit strings together use exactly $2$ bits per every vertex of the mini-tree.
Each opening parenthesis in $P_D$ and $P_U$ can be paired with the one missing in representations of the dangling trees in $T_D$ and $T_U$.
Vertices belonging to the skeleton are represented by closing parentheses in $P_D$ and $P_U$, one in each.

We can restore the original mini-tree from this representation:
\begin{algorithm}
\begin{algorithmic}
\Function{\restore}{}
	\State $v \gets null$
	\While{$P_D$ has more symbols}
		\State $v \gets$ new child of $v$
		\While{Read a symbol in $P_D$; is it an opening parenthesis}
			\State Read a tree from $T_D$, decode it and add it as a child to $v$.
		\EndWhile
	\EndWhile
	\While{$P_U$ has more symbols}
		\While{Read a symbol in $P_U$; is it an opening parenthesis}
			\State Read a tree from $T_U$, decode it and add it as a child to $v$.
		\EndWhile
		\State $v \gets \parent(v)$
	\EndWhile
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Generation of the BP and DFUDS Representations}

We recall the meaning of the constant $d$ from the definition of a significant vertex.
A dangling tree contains less than $d' = \frac{\log n}{d}$ vertices.

In the following two lemmas we show how it si possible to generate $q$ bits of BP and DFUDS representation, where $q$ is a constant dependent on the representation and constrained by $d$.

\begin{lemma}\label{l:usr-bp-skinny}
	Using an index of size $o(B)$, we can query $q' = \frac{\log n}{q}$ bits of BP representation of a skinny mini-tree provided that $i$ is a multiple of $q'$.
	The constant $q$ is restricted to:
	$$\frac{2}{q} + \frac{4}{d} < 1.$$
\end{lemma}
\begin{proof}
	We first formulate an algorithm which outputs the BP representation of the whole mini-tree.
	The algorithm is based on \restore{}; we split it into two functions \bpSkinnyDown{} and \bpSkinnyUp{}:
	
	\begin{algorithm}
	\begin{algorithmic}
	\Function{\bpSkinnyDown}{}
		\State $p_D \gets 0$%
		\Instr $t_D \gets 0$
		\While{$p_D < |P_D|$}
			\State $\out(\openingParen)$
			\While{$P_D[p_D] = \openingParen$}
				\State $t \gets \readTree(t_D)$%
				\Instr $t_D \gets t_D + |t|$%
				\Instr $p_D \gets p_D + 1$
				\State $\out(\bpRep[t])$
			\EndWhile
			\State $p_D \gets p_D + 1$ \Comment{Consume the closing parenthesis}
		\EndWhile
	\EndFunction

	\Function{\bpSkinnyUp}{}
		\State $p_U \gets 0$%
		\Instr $t_U \gets 0$
		\While{$p_U < |P_U|$}
			\While{$P_U[p_U] = \openingParen$}
				\State $t \gets \readTree(t_U)$%
				\Instr $t_U \gets t_U + |t|$%
				\Instr $p_U \gets p_U + 1$
				\State $\out(\bpRep[t])$
			\EndWhile
			\State $p_U \gets p_U + 1$ \Comment{Consume the closing parenthesis}
			\State $\out(\closingParen)$
		\EndWhile
	\EndFunction
	\end{algorithmic}
	\end{algorithm}
	
	For each $j$ we store the state of the algorithm at the point when it is about to access the arrays in order to produce the $i$-th bit of the representation:
	\begin{itemize}
		\item which function $f$ is being processed, $1$ bit;
		\item the instruction pointer $\ip$, $O(1)$ bits;
		\item the values of all local variables, $O(\log \log n)$ bits.
	\end{itemize}
	
	Using this index we can restart the course of the algorithm from any position which, related to the output, is either a parenthesis of a vertex in $P$ or the beginning of a dangling tree.
	In order to support any position of the output, we add to the index an offset $o$ which allows us to skip the first $o$ bits of which we do not need.
	
	In order to generate any $s$ bits of the BP representation, either function needs to read at most $s$ bits from $P_*$ as well as up to $s + 4d'$ bits from $T_*$.
	The term $4d'$ follows from accessing two dangling trees more than is needed.
	
	We can therefore implement the algorithms solely as two precomputed look-up tables \bpSkinnyDown{} and \bpSkinnyUp{} which get all information from the index and return the needed bits.
	The tables return correctly aligned bits ready for the output together with number of bits which they could not generate.
	The table has an additional argument $s$ which specifies the number of right-aligned bits to return.
	The total size of the index of the look-up table is $2q' + 4d' + O(\log \log n)$, which is from where the restriction on value of $q$ comes.
	
	We state the algorithm in a more general form which allows to generate $s \le q$ bits; it also returns the number of bits which it could not produce.
	Neither of these features is useful for skinny mini-trees as we always need $q$ bits, and the query cannot reach the end, because such query has already been solved.
	
	\begin{algorithm}
	\begin{algorithmic}
	\Function{\bpSubstringSkinny}{$i, s$}
		\State $r \gets 0$ \Comment{Representation buffer}
		\State $(f, \ip, p, t, o) \gets \bpIndex[\frac{i}{q'}]$
		
		\If{$f = 0$} \Comment{Function for going down}
			\State $S \gets (P_D[p:p+q'], T_D[t:t + q' + 4d'], |P_D|, |T_D|)$
			\State $(r, s) \gets \bpSkinnyDown[S, \ip, p, t, o, s]$
			\State $\ip \gets 0$%
			\Instr $p \gets 0$%
			\Instr $t \gets 0$%
			\Instr $o \gets 0$
		\EndIf
		
		\If{$s > 0$} \Comment{Function for going up}
			\State $S \gets (P_U[p:p+q'], T_U[t:t + q' + 4d'], |P_U|, |T_U|)$
			\State $(r', s) \gets \bpSkinnyUp[S, \ip, p, t, o, s]$
			\State $r \gets r \bitor r'$ \Comment{Bitwise or}
		\EndIf
		
		\State \Return{$r, s$}
	\EndFunction
	\end{algorithmic}
	\end{algorithm}
\end{proof}

\begin{lemma}\label{l:usr-dfuds-skinny}
	Using an index of size $o(B)$, we can query $q' = \frac{\log n}{q}$ bits of BP representation of a skinny mini-tree provided that $i$ is a multiple of $q'$.
	The constant $q$ is restricted to:
	$$\frac{3}{q} + \frac{4}{d} < 1.$$
\end{lemma}
\begin{proof}
	We use the same technique as in the previous lemma.
	The algorithm is a little more complicated as it needs to go through $P_D$ twice: the first time to report the degree, and the second time when the left dangling trees are reported.
	It also go through $P_U$ twice: the first time from the end to the beginning treating closing parentheses as delimiters, and the second time to output the right dangling trees.
	
	\begin{algorithm}
	\begin{algorithmic}
	\Function{\dfudsSkinnyDown}{}
		\State $p_D \gets 0$%
		\Instr $p_U \gets |P_U| - 2$%
		\Instr $t_D \gets 0$
		\While{$p_D < |P_D|$}
			\State $p_D \gets p_D$ \Comment{First we output the degree sequence}
			\While{$P_D[p_D] = \openingParen$} \Comment{Left dangling children}
				\State $p_D \gets p_D + 1$
				\State $\out(\openingParen)$
			\EndWhile
			\State $p_D \gets p_D + 1$ \Comment{Consume the closing parenthesis}
			\If{$p_D < |P_D|$} \Comment{Child in the path}
				\State $\out(\openingParen)$
			\EndIf
			\While{$P_U[p_U] = \openingParen \booland p_U \ge 0$} \Comment{Right dangling children}
				\State $p_U \gets p_U - 1$
				\State $\out(\openingParen)$
			\EndWhile
			\State $p_U \gets p_U - 1$ \Comment{Consume the closing parenthesis}
			\State $\out(\closingParen)$ \Comment{End of unary degree sequence}
			\While{$P_D[p_D] = \openingParen$} \Comment{Then we output the left dangling children}
				\State $t \gets \readTree(t_D)$%
				\Instr $t_D \gets t_D + |t|$%
				\Instr $p_D \gets p_D + 1$
				\State $\out(\dfudsRep[t])$
			\EndWhile
			\State $p_D \gets p_D + 1$ \Comment{Consume the closing parenthesis}
		\EndWhile
	\EndFunction
	\end{algorithmic}
	\end{algorithm}
	
	\begin{algorithm}
	\begin{algorithmic}
	\Function{\dfudsSkinnyDown}{}
		\State{$p_U \gets 0$%
		\Instr $t_U \gets 0$}
		\While{$p_U < |P_U|$} \Comment{Output the right dangling trees}
			\If{$P_U[p_U] = \openingParen$}
				\State $t \gets \readTree(t_U)$%
				\Instr $t_U \gets t_U + |t|$
				\State $\out(\dfudsRep[t])$
			\EndIf
			\State $p_U \gets p_U + 1$ \Comment{Consume the closing parenthesis}
		\EndWhile
	\EndFunction
	\end{algorithmic}
	\end{algorithm}
	
	The index contains record about three local variables.
	The look-up table \dfudsSkinnyDown{} requires access to $q'$ bits of $P_U$ and $P_D$, and to $q' + 4d'$ bits of $T_D$, while \dfudsSkinnyDown{} needs $q'$ bits of $P_U$, and $q' + 4d'$ bits of $T_U$.
	The maximum total size of the index is $3q' + 4d' + O(\log \log n)$, which is from where the restriction on value of $q$ comes.	
	
	The algorithm \dfudsSubstringSkinny{} for the DFUDS representation is similar to \bpSubstringSkinny{}.
	The difference is only in the data which are provided to the look-up tables.
\end{proof}

The better calculation of the size of the index proved to be beneficial.
If we set $d = 16$, which was the value originally proposed in \cite{farzan2009universal}, we set $q = 3$ for BP and to $q = 5$ for DFUDS representation.
Both values are significantly better than the former $q = 8$ for BP and $q = 24$ for DFUDS representation.

\subsection{General Mini-Trees}

If the skeleton is a general tree, we decompose it iteratively into paths.
We first remove the leftmost path connecting the root with the first skeleton leaf; we call it a \emph{left-leaning path}.
For each tree in the rest of the skeleton, we remove its rightmost path connecting the root with the last skeleton leaf; we call it a \emph{right-leaning path}.
We repeat this until every vertex of the skeleton is in a left-leaning or a right-leaning path.

The decomposition keeps subtrees of non-significant vertices connected to their parent, which is now in a path; they are again called left and right dangling trees.
A path together with its dangling trees can be viewed as a skinny mini-tree.
There are $O\left(\frac{B}{\log n}\right)$ paths as each of them ends in a leaf.
We assign each path a number starting with $0$.

The paths are connected with each other in three possible ways:
\begin{itemize}
	\item A left-leaning path can have left-leaning and right-leaning paths connected to the right.
	If there are more of them connected to one vertex, we store only the leftmost one.
	
	\item A right-leaning path can have left-leaning paths connected to the left.
	Again, if there are more of them connected to the same vertex, we store only the leftmost one.
	
	\item All paths except for one have a \emph{next path}.
	The next path is either the path containing the right sibling of its root if it exists, or the path containing the parent of its root.
	The only path which does not have a next path is the path containing the mini-tree root.
\end{itemize}

In the skinny mini-trees we could uniquely reference any bit of the representation by the state of the algorithm and the offset $o$.
In the case of general mini-trees, we extend the index by the number of the path.
The size of the index record is $O(\log \log n)$ and we call it a \emph{reference}.

\subsubsection{Path Structures}

First, we add opening parentheses to the bit strings $P_D$ and $P_U$ for all connected paths.
Without this change reporting the vertex degree in the DFUDS representation would be wrong.
This change adds $O\left(\frac{B}{\log n}\right)$ bits because the each path is connected to at most one other path.
The root of a path (except for the path containing the mini-tree root) is represented by $3$ bits in total.

For each path we define arrays $C_D$ and $C_U$ which mark the positions of the parentheses which we have just added.
Note that only one of the arrays is non-empty since left-leaning paths have connections only to the right -- in $C_U$, and right-leaning paths only to the left -- in $C_D$.
In order to find the position of the closest connection, we turn the arrays $C_D$ and $C_U$ into a collection of compressed arrays using the operation \succ{}.
The values in the arrays are the references denoting where to continue; we store two versions of them: for BP and for DFUDS representation.

There are $O(B)$ elements in the each collection of compressed arrays in total since they contain the same number of elements as the arrays $P_*$.
Each reference in the compressed arrays refers to the root of a connected path, therefore each of them occurs in a single run, and the total number of them is bounded by the number of paths.
Each collection of compressed arrays takes $o(B)$ bits of space.

\begin{description}
	\item[Path]
	The path structure contains the following fields:
	\begin{description}
		\item[$k$]
		The number of the path.
		
		\item[$P_D, P_U, T_D, T_U$]
		As before.
	
		\item[$\bpNext, \dfudsNext$]
		References to the next path for both BP and DFUDS representations.
	\end{description}
	
	\item[Mini-tree]
	The fields which are stored for the whole mini-tree.
	\begin{description}
		\item[$\bpIndex, \dfudsIndex$]
		These are the indices from the algorithms \bpSubstringSkinny{} and \dfudsSubstringSkinny{} generalized to incorporate the path number.
		They contain a reference for each multiple of $q'$.
		
		
		\item[$\bp\_C_D, \bp\_C_U, \dfuds\_C_D, \dfuds\_C_U$]
		The collections of compressed arrays which contain references to connected paths for all paths.
		
		\item[Paths]
		Concatenated structures for paths together with a table of their offsets.
	\end{description}
\end{description}

\subsubsection{Algorithm for the General Mini-Trees}

We extend the algorithm for skinny mini-trees by several modifications:
\begin{itemize}
	\item It is provided the reference (the state of the algorithm) instead of finding it in the index itself.
	
	\item It finds the position $c$ of the closest connected path in the direction of traversal and provides it to the look-up table.
	
	\item Whenever the algorithm captured by the look-up table encounters the position $c$, it shall stop and return the reason.
	
	\item The look-up tables return more information:
	\begin{itemize}
		\item the number of bits which they could not generate;
		\item the buffer containing the generated bits;
		\item the situation which lead to the end:
		\begin{enumerate}
			\item the requested number of bits was generated;
			\item a turn from direction down to up is requested;
			\item a switch to a connected path is necessary;
			\item a switch to the next path is requested.
		\end{enumerate}
	\end{itemize}
	
	\item If the reason is a switch (3) or (4), a recursive call with the number of bits left to be generated is made.
\end{itemize}

We present an algorithm returning a block of $q'$ bits of the BP representations starting at a position which is a multiple of $q'$.
The same restrictions to $q$ applies as in the lemma \ref{l:usr-bp-skinny}.
A similar algorithm is for DFUDS representation (with its constraint on the value of $q$).

\begin{algorithm}
\begin{algorithmic}
\Function{\bpSubstring}{$I, s$} \Comment{$I$ is the record in the global index}
	\State $(k, f, \ip, p, t, o) \gets I$
	
	\If{$f = 0$} \Comment{Function for going down}
		\State $S \gets (k.P_D[p:p+q'], k.T_D[t:t + q' + 4d'], |k.P_D|, |k.T_D|)$
		\State $c \gets \runLast(\bp\_C_D, k, p)$%
		\Instr $C \gets \bp\_C_D[k, c]$
		\State $(r, s, e) \gets \bpSkinnyDown[S, I, s, c]$
	\ElsIf{$f = 1$} \Comment{Function for going up}
		\State $S \gets (k.P_U[p:p+q'], k.T_U[t:t + q' + 4d'], |k.P_U|, |k.T_U|)$
		\State $c \gets \runLast(\bp\_C_U, k, p)$%
		\Instr $C \gets \bp\_C_U[k, c]$
		\State $(r, s, e) \gets \bpSkinnyUp[S, I, s, c]$
	\EndIf
	
	\If{$e = 2$} \Comment{Switch direction}
		\State{$(r', s) \gets \bpSubstring((k, 1, 0, 0, 0, 0), s)$}
		\State $r \gets r \bitor r'$
	\ElsIf{$e = 3$} \Comment{Switch to connection}
		\State{$(r', s) \gets \bpSubstring(C, s)$}
		\State $r \gets r \bitor r'$
	\ElsIf{$e = 4 \booland k.\bpNext \ne -1$} \Comment{Switch to next}
		\State{$(r', s) \gets \bpSubstring(k.\bpNext, s)$}
		\State $r \gets r \bitor r'$
	\EndIf
	
	\State \Return{$r, s$}
\EndFunction
\end{algorithmic}
\end{algorithm}

\bigbreak

It only remains to argue that the depth of the recursion is constant.
We inspect the graph of transitions between paths.

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.8]{usr-trans}
	\caption{Graph of the transitions between paths and directions of the traversal}
\end{figure}

First we observe that all cycles in the graph contain the edges labeled ``Turn''.
We focus on the transitions of the direction of a path traversal from ``down'' to ``up''.

\begin{lemma}
	When the direction of the path traversal changes from ``down'' to ``up'', at least $2d'$ bits of the representation are generated.
\end{lemma}
\begin{proof}
	As the initial reference in the global index can lead anywhere, we start the analysis after the first transition.
	All references leading to a left-leaning path traversed down target its root.
	In case of the right-leaning path traversed down, there are three possible references to it:
	\begin{itemize}
		\item If the path was referenced as a right connection, then its root was the target.
		\item If the path was referenced as the next from a sibling of its root, then its root was targeted.
		\item If the path was referenced as the next from other vertex, then it was from the root of its left connection.
		Because of the path decomposition algorithm, this left-leaning path cannot be connected to the skeleton leaf.
	\end{itemize}

	In all these cases the whole subtree of the skeleton leaf is processed.
	Since the subtree contains $d'$ vertices, at least $2d'$ bits of representation are generated.
\end{proof}

From the lemma and from the lengths of the cycles follows that at most $3 \frac{q'}{2d'} + 2 = O(\frac{d}{q}) = O(1)$ recursive calls are required.
The additional $2$ is the number of recursive calls before the first cycle.

Since we want to generate as many bits as possible, we want to set $q$ small, however that results in deeper recursion and longer running time.
Setting $q \ge \frac{d}{2}$ ensures that a single ``Turn'' generates enough bits.

\subsection{Micro-Tree Representation}

The mini-tree is decomposed into micro-trees as it is usual for the Tree Covering representation.
We reuse the lemma \ref{l:usr-runs} which in this case claims that the BP representation of a micro-tree forms at most four runs in the BP representation of a mini-tree.
We prefer the BP representation over DFUDS because no degree adjustment of the root is necessary.

For each micro-tree $(\tau_1, \tau_2)$ we store positions of the beginning and the end of each run of $\tau_2$ withing the BP representation of the mini-tree $\tau_1$.
If the micro-tree contains a dummy vertex, an adjustment of the run boundaries by $1$ is needed.
The length of each run is bounded by the size of the micro-tree, which is less then $\frac{\log n}{2}$, therefore $O(1)$ queries of the BP representation are sufficient.
If the micro-tree is not a primary one, an opening and a closing parentheses are added.

The size of BP representation of a micro-tree can be calculated from the stored offsets of the runs and its primarity.
Because of the small size of the micro-tree BP representation, we can use a look-up table to transcode it into any other representation which is native for the TC data structure.

\subsection{Final Thoughts}

The universal succinct representation provides a way how to combine several data structures which we have shown in the previous sections.
As two of the three representations (BP/FF, DFUDS, TC) support nearly the same set of operations, its benefits consist in allowing to choose the most space or time efficient implementation of an operation out of several alternatives.