# Space-Efficient Fully Dynamic DFS
## 6 Compression of Data Structures
### Range Next Value Query  
First, we show a data structure of \((2m+o(m))\log n\) bits, which can be derived immediately from the existing results.  
It is already known that the ORS (ORP) query on a \(k\times\sigma\) grid \(\mathcal{G}^{\prime}\) with \(k\) points, where all points differ in \(x\)-coordinates, can be solved efficiently with wavelet tree [23]. Now we describe this method in detail. The method is to build an integer array \(S[1...k]\) where \(S[i]\) (\(1\leq i\leq k\)) is the \(y\)-coordinate of the point whose \(x\)-coordinate is \(i\). Then the ORS (ORP) query is converted to the following query on \(S\).  
An integer sequence \(S[1...l]\) is given. Then for any interval \([a,b]\subseteq[1,l]\) and integer \(p\) (\(q\)), the range next (previous) value query returns one of the smallest (largest) elements among the ones in \(S[a...b]\) which are not less than \(p\) (not more than \(q\)). If there is no such element, the query should return \(\emptyset\). We abbreviate it as RN (RP) query.  
These queries can be efficiently solved with the wavelet tree \(\mathcal{W}\) for \(S\); if \(S[i]\in[0,\sigma-1]\) for all \(i=1,\ldots,l\), they can be solved with \(O(\log\sigma)\)rank and select queries on \(\mathcal{W}\)[23]. The pseudocode for solving RN query by the wavelet tree for \(S\) is given in Algorithm 1. In Algorithm 1, \(\mathit{left}(v)\) and \(\mathit{right}(v)\) stand for the left and right child of the node \(v\), respectively. When calling RN(_root_, \(p\), \([a,b]\), \([0,\sigma-1]\)), we can obtain the answer for the RN query with \([a,b]\) and \(p\). Here a pair of the position and the value of the element is returned. If \((0,-1)\) is returned, the answer for the RN query is \(\emptyset\). The RP queries on \(S\) can be solved in a similar way using the same wavelet tree as the RN queries.  
The ORS query on \(\mathcal{G}^{\prime}\) with \(R=[x_{1},x_{2}]\times[y_{1},y_{2}]\) can be answered by solving the RN query on \(S\) with \([a,b]=[x_{1},x_{2}]\) and \(p=y_{1}\). If the RN query returns \(\emptyset\), the answer for the ORS query is also \(\emptyset\). If the RN query returns an element, the answer is \(\emptyset\) if the value of this element is larger than \(y_{2}\), or the point corresponding to this element otherwise. Similarly, the ORP query on \(\mathcal{G}^{\prime}\) can be converted to the RP query on \(S\).  
Although in the grid \(\mathcal{G}\), on which we want to solve ORS (ORP) queries, some points share the same \(x\)-coordinate, it is addressed by preparing a bit vector \(B\) in the same way as the proof of Lemma 4. \(B\) enables us to convert \(x\)-coordinates. Here the integer sequence \(S[1...2m]\) consists of the \(y\)-coordinates of the points on \(\mathcal{G}\) sorted by the corresponding \(x\)-coordinates. The required space of the wavelet tree is \((2m+o(m))\log n\) bits since there are \(k=2m\) points on \(\mathcal{G}\) and the \(y\)-coordinates vary between \([0,n-1]\). Hence now we obtain a data structure of \((2m+o(m))\log n\) bits to solve \(Q\) and \(Q^{\prime}\) (note that the bit vector requires only \(o(m)\log n\) bits as described in the proof of Lemma 4).