# Space-Efficient Fully Dynamic DFS
## 6 Compression of Data Structures
### Range Leftmost Value Query  
Next, we show another way to compress the data structure to \((m+o(m))\log n\) bits. This is achieved by solving _range leftmost (rightmost) value query_ with a wavelet tree. This query appears in the preliminary version [10] of this paper. In the preliminary version, this query and the RN (RP) query (Definition 4) is used simultaneously to obtain a data structure of \((m+o(m))\log n\) bits. Although we no longer need to use this query to halve the required space as described in Section 6.2, this query stillgives us another way to compress the data structure. Moreover, this query is of independent interest since its application is beyond the dynamic DFS algorithm, as described later. The range leftmost (rightmost) value query is defined as follows. Definition 5: An integer sequence \(S[1...l]\) is given. Then for any interval \([a,b]\subseteq[1,l]\) and two integers \(p\leq q\), the range leftmost (rightmost) value query returns the leftmost (rightmost) element among the ones in \(S[a...b]\) with a value not less than \(p\) and not more than \(q\). If there is no such element, the query should return \(\emptyset\). We abbreviate it as RL (RR) query. This RL (RR) query is a generalization of the query of Claim 3 in the sense that the value of elements we focus varies between \([p,q]\) instead of being fixed to just \(c\). Moreover, the RL (RR) query is a generalization of a _prevLess query_[24], which is the RR query with \(a=1\) and \(p=0\). It is already known that the prevLess query can be efficiently solved with the wavelet tree for \(S\)[24]. First we describe the idea to use RL (RR) query for solving \(Q\) and \(Q^{\prime}\). Here we consider the symmetric variant of ORS (ORP) query, which is almost the same as ORS (ORP) query except that it returns one of the points whose \"\(x\)-coordinate\" is the smallest (largest) within \(R\) (we call it symmetric ORS (ORP) query). The motivation to consider symmetric ORS (ORP) queries comes from transposing the query rectangle of normal ORS (ORP) queries. Since \(\mathcal{G}\) is symmetric, the (normal) ORS query on \(\mathcal{G}\) with rectangle \(R=[x_{1},x_{2}]\times[y_{1},y_{2}]\) is equivalent to the symmetric ORS query on \(\mathcal{G}\) with rectangle \(R^{\top}=[y_{1},y_{2}]\times[x_{1},x_{2}]\). When transposing the rectangle, we can focus on the lower triangular part \(\mathcal{G}_{l}\) instead of the upper triangular part \(\mathcal{G}_{u}\), as described below. Let \(S_{l}\) and \(B_{l}\) be an integer sequence and a bit vector constructed from \(\mathcal{G}_{l}\) in the same manner as \(S_{u}\) and \(B_{u}\). \(B_{l}\) enables us to convert between the \(x\)-coordinate on \(\mathcal{G}_{l}\) and the position in \(S_{u}\). Then it can be observed that the symmetric ORS query on \(\mathcal{G}_{l}\) with \(R=[x_{1},x_{2}]\times[y_{1},y_{2}]\) can be answered by solving the RL query on \(S_{l}\) with \([a,b]=[x^{\prime}_{1},x^{\prime}_{2}]\) and \([p,q]=[y_{1},y_{2}]\), where \([x^{\prime}_{1},x^{\prime}_{2}]\) is the interval of the position in \(S_{l}\) corresponding to \([x_{1},x_{2}]\). If the RL query returns \(\emptyset\), the answer for the symmetric ORS query is also \(\emptyset\). Otherwise the answer can be obtained by converting the returned position in \(S_{l}\) to the \(x\)-coordinate on \(\mathcal{G}_{l}\) by \(B_{l}\). In this reduction \"leftmost\" means \"the smallest \(x\)-coordinate\". Similarly, a symmetric ORP query on \(\mathcal{G}_{l}\) can be converted to an RR query on \(S_{l}\). With this conversion from the symmetric ORS (ORP) query to the RL (RR) query, we can prove the following lemma which is a lower triangular version of Lemma 6. Lemma 7: _Any ORS (ORP) query which appears in the reduction of Lemma 3 can be answered by solving one RL (RR) query, or by solving one_ rank _and one_ select _queries, on \(S_{l}\)._  
Proof: From Claim 2, the rectangles of the ORS queries corresponding to \(Q\) is all inside the upper triangular part.