# Space-Efficient Fully Dynamic DFS
## 6 Compression of Data Structures
### Range Leftmost Value Query
Therefore, when we transpose them, they are inside the lower triangular part. Since the symmetric ORS query can be converted into the RL query as described above, it is enough for solving \(Q\). In solving \(Q^{\prime}\), there may be query rectangles inside the upper triangular part. However, they are solved by one rank and one select queries on \(S_{l}\), in the same way as Claim 3. Next we describe how to solve RL (RR) queries with a wavelet tree. We prove the following lemma, by referring to the method to solve prevLess [24] by a wavelet tree. Lemma 8: _An integer sequence \(S[1...l]\) is given. Suppose that \(S[i]\in[0,\sigma-1]\) for all \(i=1,\ldots,l\). Then using the wavelet tree for \(S\), both RL and RR queries can be answered in \(O(\log\sigma)\) time for each._  
Proof: We show that with the pseudocode given in Algorithm 2. First we show the correctness. In the arguments of RL, \(v\) is the node of the wavelet tree we are present, and \([\alpha,\omega]\) is the interval of symbols \(v\) corresponds to (i.e., \([\alpha,\omega]=[l_{v},r_{v}]\)). We claim the following, which ensures us that the answer for the RL query can be obtained by calling \(\text{RL}(\textit{root},[p,q],[a,b],[0,\sigma-1])\). **Claim 4**. : _For any node \(v\) of wavelet tree and four integers \(a,b,p,q\), calling \(\mathrm{RL}(v,[p,q],[a,b],[l_{v},r_{v}])\) yields the position of the answer for the RL query on \(S_{v}\). If the answer for the RL query is \(\emptyset\), this function returns \(0\)._  
Proof. : We use an induction on the depth of the node \(v\). The base case is \([l_{v},r_{v}]\cup[p,q]=\emptyset\) or \([l_{v},r_{v}]\subseteq[p,q]\) (note that either of them must occur when \(l_{v}=r_{v}\), so if \(v\) is a leaf node the basis case must happen). For the former case, the answer is obviously \(\emptyset\). For the latter case, the answer is \(a\) since all elements in \(S_{v}[a...b]\) have value between \([l_{v},r_{v}]\subseteq[p,q]\). In these cases, the answer is correctly returned with lines 2-3 of Algorithm 2. Now we proceed to the general case. Let \(l(v)=\mathit{left}(v)\), \(r(v)=\mathit{right}(v)\) and \(\gamma=\lfloor(l_{v}+r_{v})/2\rfloor\). Then \([l_{l(v)},r_{l(v)}]=[l_{v},\gamma]\) and \([l_{r(v)},r_{r(v)}]=[\gamma+1,r_{v}]\). Therefore, the elements in \(S_{v}[a...b]\) with a value between \([l_{v},\gamma]\) appear in the left child \(S_{l(v)}[a_{l}...b_{l}]\), and those with a value between \([\gamma+1,r_{v}]\) appear in the right child \(S_{r(v)}[a_{r}...b_{r}]\). Here \(a_{l},b_{l},a_{r}\) and \(b_{r}\) can be calculated by \(\mathrm{rank}\) queries on \(B_{v}\): \([a_{l},b_{l}]=[\mathrm{rank}_{0}(B_{v},a-1)+1,\mathrm{rank}_{0}(B_{v},b)]\) and \([a_{r},b_{r}]=[\mathrm{rank}_{1}(B_{v},a-1)+1,\mathrm{rank}_{1}(B_{v},b)]\). It can be observed that the element \(S_{v}[i^{\prime}]\) of \(S_{v}\) corresponding to the leftmost element \(S_{l(v)}[i]\) in \(S_{l(v)}[a_{l},b_{l}]\) with a value within \([p,q]\) is also the leftmost element in \(S_{v}[a...b]\) with a value within \([p,q]\cap[l_{v},\gamma]\). Here \(i\) can be obtained by \(\mathrm{RL}(l(v),[p,q],[a_{l},b_{l}],[l_{v},\gamma])\) (induction hypothesis) and \(i^{\prime}=\mathtt{select}_{0}(B_{v},i)\). Similarly, the element \(S_{v}[j^{\prime}]\) of \(S_{v}\) corresponding to the leftmost element \(S_{r(v)}[i]\) in \(S_{r(v)}[a_{r},b_{r}]\) with a value within \([p,q]\) is also the leftmost element in \(S_{v}[a...b]\) with a value within \([p,q]\cap[\gamma+1,r_{v}]\). Again \(j\) can be obtained by \(\mathrm{RL}(r(v),[p,q],[a_{r},b_{r}],[\gamma+1,r_{v}])\) (induction hypothesis) and \(j^{\prime}=\mathtt{select}_{1}(B_{v},j)\). Hence \(S_{v}[\min\{i^{\prime},j^{\prime}\}]\) is the leftmost element we want to know. Now the answer is correctly returned with lines 4-10 of Algorithm 2: lines 7-10 cope with the case the RL function returns \(0\). Next we discuss the time complexity when calling \(\mathrm{RL}(v,[p,q],[a,b],[l_{v},r_{v}])\). We show that for each level (depth) of the wavelet tree the function visits at most four nodes.