# Space-Efficient Fully Dynamic DFS
## 6 Compression of Data Structures
### Halving Required Space  
Next, we propose a data structure of \((m+o(m))\log n\) bits to solve \(Q\) and \(Q^{\prime}\). The data structure shown in Section 6.1 has information of both directions for each edge of \(G\) since \(G\) is an undirected graph. This seems to be redundant, thus we want to hold information of only one direction for each edge. In fact, the placement of points on \(\mathcal{G}\) is symmetric since the adjacency matrix of \(G\) is also symmetric. So now we consider, of the grid \(\mathcal{G}\), the _upper triangular part_\(\mathcal{G}_{u}\) and the _lower triangular part_\(\mathcal{G}_{l}\); a grid \(\mathcal{G}_{u}\) inherits from \(\mathcal{G}\) the points within the region the \(x\)-coordinate is larger than the \(y\)-coordinate, and \(\mathcal{G}_{l}\) is defined in the same manner. Since \(G\) has no self-loops, \(\mathcal{G}_{u}\) and \(\mathcal{G}_{l}\) have \(m\) points for each. Now we show that we can use \(\mathcal{G}_{u}\) as a substitute for \(\mathcal{G}\). Let \(S_{u}[1...m]\) be an integer sequence which contains the \(y\)-coordinates of the points on \(\mathcal{G}_{u}\) sorted by the corresponding \(x\)-coordinates. Let \(B_{u}\) be a bit vector \(0^{d_{0,u}}10^{d_{1,u}}1\cdots 0^{d_{n-1}=1}\), where \(d_{i,u}\) is the number of occurrences of \(i\) in \(S_{u}\). \(B_{u}\) enables us to convert the \(x\)-coordinate on \(\mathcal{G}\) to the position in \(S_{u}\) and vice versa in \(O(1)\) time. Figure 4 is an example of the grid \(\mathcal{G}\) and its upper triangular part \(\mathcal{G}_{u}\). Here we should observe that \(\mathcal{G}_{u}\) has half as much point as \(\mathcal{G}\) and thus the length of \(S_{u}\) is halved from \(S\). Figure 4: **(Left)** an example of the grid \(\mathcal{G}\) and its corresponding array \(S\) and bit vector \(B\). Please note that this grid corresponds to the graph in Figure 3. **(Right)** the upper triangular part \(\mathcal{G}_{u}\) and its corresponding array \(S_{u}\) and bit vector \(B_{u}\). **Lemma 6**: _Any ORS (ORP) query which appears in the reduction of Lemma 3 can be answered by solving one RN (RP) query, or by solving one_ rank _and one_ select _queries, on \(S_{u}\)._  
We give a proof for only ORS queries since that for ORP queries is almost same. It can be observed that if the query rectangle of the ORS query is inside the upper triangular part of \(\mathcal{G}\), this ORS query can be converted to an RN query on \(S_{u}\) in the same way as Section 6.1, since \(\mathcal{G}_{u}\) contains all points inside the upper triangular part in \(\mathcal{G}\). The below claim ensures us that any ORS query related to \(Q\) can be converted to the RN query on \(S_{u}\). **Claim 2**: _The rectangles appearing in Claim 1 are all inside the upper triangular part of \(\mathcal{G}\), i.e., these rectangles are of the form: \([x_{1},x_{2}]\times[y_{1},y_{2}]\) with \(y_{1}\leq y_{2}<x_{1}\leq x_{2}\)._  
It can be easily observed that \(t_{b}\), appearing in the interval \([t_{b},t_{e}]\) corresponding to the vertices of a subtree \(T(w)\), equals to \(f(w)\). Since \(\operatorname{LCA}(y,w)\preceq p\prec w\), \(f(\operatorname{LCA}(y,w))\leq f(p)<f(w)\) and thus \([t_{b},t_{e}]\times[f(x),f(\operatorname{LCA}(y,w))]\) is inside the upper triangular part. In solving \(Q^{\prime}\), there may be query rectangles inside the lower triangular part. However, these rectangles are of the form: \([f(w),f(w)]\times[a,b]\) with \(f(w)<a\leq b\). Transposing this rectangle, it is inside the upper triangular part and the problem becomes like the following: for a rectangle \(R=[a,b]\times[c,c]\) (with \(c<a\leq b\)) on \(\mathcal{G}_{u}\), we want to know the point whose \"\(x\)-coordinate\" is the smallest within \(R\). Converting the \(x\)-coordinate to the position in \(S_{u}\) by \(B_{u}\), this problem is equivalent to the following problem: to find the leftmost element among ones in \(S_{u}[a^{\prime}...b^{\prime}]\) with a value just \(c\).