# Space-Efficient Fully Dynamic DFS
## 6 Compression of Data Structures
### Range Leftmost Value Query
At the top level we visit only one node _root_. At level \(k\), the general case occurs at most two times: it may occur when \([l_{v},r_{v}]\) contains the endpoints of \([p,q]\). Thus, at level \(k+1\) the RL function is called at most \(2\times 2=4\) times. Since the wavelet tree has depth \(\lceil\log\sigma\rceil\), RL function is called \(O(\log\sigma)\) times. For each node, all calculation other than the recursion can be done in \(O(1)\) time, so the overall time complexity is \(O(\log\sigma)\). The same argument can be applied for the RR query. This completes the proof. ```
1:function\(\mathrm{RL}(v,[p,q],[a,b],[a,\omega])\)
2:if\(a>b\) or\([\alpha,\omega]\cap[p,q]=\emptyset\)then return\(0\)
3:if\([\alpha,\omega]\subseteq[p,q]\)then return\(a\)
4:\(\gamma\leftarrow\lfloor(\alpha+\omega)/2\rfloor\)
5:\(i\leftarrow\mathrm{RL}(\mathit{left}(v),[p,q],[\mathrm{rank}_{0}(B_{v},a-1)+1,\mathrm{rank}_{0}(B_{v},b)],[\alpha,\gamma])\)
6:\(j\leftarrow\mathrm{RL}(\mathit{right}(v),[p,q],[\mathrm{rank}_{1}(B_{v},a-1)+1,\mathrm{rank}_{1}(B_{v},b)],[\gamma+1,\omega])\)
7:if\(i\
eq 0\)and\(j\
eq 0\)thenreturn\(\mathtt{min}(\mathtt{select}_{0}(B_{v},i),\mathtt{select}_{1}(B_{v},j))\)
8:elseif\(i\
eq 0\)thenreturn\(\mathtt{select}_{0}(B_{v},i)\)
9:elseif\(j\
eq 0\)thenreturn\(\mathtt{select}_{1}(B_{v},j)\)
10:elsereturn\(0\)
11:endfunction
```  
**Algorithm 2** Range Leftmost Value by Wavelet Tree  
Lemmas 7 and 8 imply another way to achieve Corollary 2. Finally, we discuss the application of RL (RR) query beyond the dynamic DFS algorithm. Let us consider ORS and ORP queries on an \(l\times l\) grid \(\mathcal{S}\) whose placement of points is symmetric. Suppose that there are \(d\) points on a diagonal line of \(\mathcal{S}\) (we call them _diagonal points_) and \(2k\) points within the other part of \(\mathcal{S}\). Generally, there is no assumption on query rectangles such as Claim 2, so with only RN (RP) queries we cannot remove the points within the lower triangular part of \(\mathcal{S}\). However, using RL (RR) queries as well as RN (RP) queries, we can consider only the upper triangular and the diagonal parts of \(\mathcal{S}\). The idea, which is very similar to the method in the preliminary version [10] of this paper,is as follows. First, for a query rectangle \(R=[x_{1},x_{2}]\times[y_{1},y_{2}]\) of the ORS (ORP) query, we solve the corresponding RN (RP) query. Second, for the transposed query rectangle \(R^{\top}=[y_{1},y_{2}]\times[x_{1},x_{2}]\), we solve the corresponding RL (RR) query, and \"transpose\" the answer. Finally, we combine these two answers: choose the one with smaller (larger) \(y\)-coordinate. Let \(S_{ud}\) and \(B_{ud}\) be an integer sequence and a bit vector constructed from the upper triangular and the diagonal parts of \(\mathcal{S}\) in the same manner as \(S_{u}\) and \(B_{u}\). A wavelet tree for \(S_{ud}\) can solve RN, RP, RL and RR queries on \(S_{ud}\) and occupies \((k+d+o(k)+o(d))\log l\) bits, since the diagonal part has \(d\) points and the upper triangular part has \(k\) points. Because the space required for \(B_{ud}\) is not a matter, now we obtain a space-efficient data structure for solving ORS and ORP queries on \(\mathcal{S}\). If \(d=0\), the required space of the data structure is actually halved from using wavelet tree directly (\((2k+d+o(k)+o(d))\log n\) bits). If \(d\) is large, we can further compress the space from \((k+d+o(k)+o(d))\log l\) bits by treating diagonal points separately. Let \(B_{d}[1..l]\) be a bit vector such that \(B_{d}[i]=1\) if there exists a point on coordinates \((i,i)\) and \(B_{d}[i]=0\) otherwise. For a query rectangle \(R=[x_{1},y_{1}]\times[x_{2},y_{2}]\), let \([a,b]=[\max\{x_{1},y_{1}\},\min\{x_{2},y_{2}\}]\). Then it can be easily observed that \(R\) contains diagonal lines from \((a,a)\) to \((b,b)\) if \(a\leq b\) and \(R\) has no diagonal points otherwise. Therefore if \(a\leq b\), a diagonal point with smallest (largest) \(y\)-coordinate within \(R\) can be obtained by one rank and one select query on \(B_{d}\).