# Space-Efficient Fully Dynamic DFS
## 4 Query Reduction to Orthogonal Range Search Problem
### Efficient Reduction  
Next we show the following: (a) the query \(Q(T(w),x,y)\) can be converted to single (not \(O(\log n)\)) ORS/ORP query for any \(w,x,y\), and (b) the deletion of points from \(\mathcal{G}\) need not be supported. Note that the idea to partially achieve (a) is first proposed by [PERSON] et al. (2019) and we use a part of it. However, the solution of the query \(Q\) of [PERSON] et al. (2019) deals with only the case \(T(w)\) is hanging from \(path(x,y)\) (that is, the case (ii) in Figure 1 explained later). Thus we here extend this to deal with an arbitrary case. The goal is to prove the following lemma. Lemma 3: _Suppose there exists a data structure \(\mathcal{D}\) which can solve both ORS and ORP queries on \(\mathcal{G}\) in \(O(f)\) time for each. Then for any three vertices \(w,x,y\), the query \(Q(T(w),x,y)\) can be solved in \(O(f)\) time with \(\mathcal{D}\). Similarly, for any \(w,x,y\) the query \(Q^{\prime}(w,x,y)\) can be answered in \(O(f\log n)\) time with \(\mathcal{D}\). Please note that \(\mathcal{D}\) need not support deletion of points from \(\mathcal{G}\)._  
First we show (a) when \(U=\emptyset\) (later this assumption is removed). Here we define some symbols for convenience: for two vertices \(a\) and \(b\) in \(G\), \(a\prec b\) means \(a\) is an ancestor of \(b\) in \(T\), \(a\preceq b\) means \(a\prec b\) or \(a=b\), and \(a\parallel b\) means neither \(a\preceq b\) nor \(b\preceq a\) holds, i.e., \(a\) and \(b\) have no ancestor-descendant relation. Let \(p=par(w)\). Please note that it is confirmed that \(w\) always has a parent because if \(w\) is the root of \(T\), \(T(w)=T\) spans all vertices of \(G\) and has some common vertices with any \(path(x,y)\), which contradicts the assumption (see Definition 2). Now we assume \(x\preceq y\) (the case \(y\prec x\) is considered at last). Then the configurations of \(T(w)\) and \(path(x,y)\) can be classified into five patterns in terms of \(x,y\) and \(p\) as drawn in Figure 1: (i) \(p\prec x\preceq y\), (ii) \(x\preceq p\preceq y\), (iii) \(x\preceq y\prec p\), (iv) \(x\parallel p\) and (v) \(x\prec p\) and \(y\parallel p\). Now we show the following. Claim 1: _For all cases from (i) to (v), the answer for \(Q(T(w),x,y)\) can be obtained by solving the ORS query on \(\mathcal{G}\) with \(R=[t_{b},t_{e}]\times[f(x),f(\operatorname{LCA}(y,w))]\), where \([t_{b},t_{e}]\) is the interval the vertices of \(T(w)\) occupy in the vertex numbering and \(\operatorname{LCA}(y,w)\) is the lowest common ancestor of \(y\) and \(w\) in \(T\)._  
Proof: First, for the cases (i) and (iv), the answer for \(Q(T(w),x,y)\) is \(\emptyset\) since if such edge exists, it becomes a cross edge and thus refutes DFS property. For these cases, since \(\operatorname{LCA}(y,w)\) comes above \(x\) and thus \(f(x)>f(\operatorname{LCA}(y,w))\), the ORS query also returns \(\emptyset\), which correctly answers \(Q(T(w),x,y)\). For other cases ((ii), (iii) and (v)), \(\operatorname{LCA}(y,w)\) lies on \(path(x,y)\). Here all edges between \(T(w)\) and \(path(x,y)\) are indeed between \(T(w)\) and \(path(x,\operatorname{LCA}(y,w))\) due to DFS property. It may be that the interval \([f(x),f(\operatorname{LCA}(y,w))]\) contains some vertex ids of the vertices of branches forking from \(path(x,\operatorname{LCA}(y,w))\), which happens when these branches are traversed prior to \(y\) and \(w\) in \(\mathcal{L}\). This does not cause trouble because there are no edges between \(T(w)\) and these branches again due to DFS property. Hence \(R\) contains all edges between \(T(w)\) and \(path(x,y)\) and no other edges, when we see \(\mathcal{G}\) as an adjacency matrix of \(G\). Thus, reporting a point whose \(y\)-coordinate is the smallest within \(R\) yields an answer for \(Q(T(w),x,y)\). Here note that the LCA query can be solved in \(O(1)\) time with a data structure of \(O(n\log n)=o(m)\log n\) bits built in \(O(n)\) time (Kurz and Kurz, 2019). Therefore Claim 1 holds.