total query time is $q(n)=O(\log^{{\varepsilon}}n)+ q(\sqrt{n\log^3n})= O(\log^{{\varepsilon}}n\log\log n)$.

A five-sided query $[a,b]\times [h_1,h_2]\times [0,z]$ is processed in a similar way. If a query is entirely contained in one horizontal or vertical slab, we answer the query using the data structure for that slab. If a query intersects several horizontal slabs and several vertical slabs, we split the query range into five parts. Let $V_a$ and $V_b$ denote the vertical slabs that contain $a$ and $b$ respectively; let $H_1$ and $H_2$ denote the horizontal slabs that contain $h_1$ and $h_2$. We answer three-sided queries $[a,+\infty)\times [h_1,h_2]$ and $[0,b]\times [h_1,h_2]$ on slabs $V_a$ and $V_b$ respectively. We answer two other three-sided queries $[a,b]\times [h_1,+\infty)$ and $[a,b]\times [0,h_2]$ on slabs $H_1$ and $H_2$. The central part of the query can be answered using the top data structure $D^t$. The total query time is dominated by three-sided queries, $q(n)=O(\log^{{\varepsilon}} n\log\log n)$. We can reduce the time to $O(\log^{{\varepsilon}} n)$ by replacing ${\varepsilon}$ with an arbitrary ${\varepsilon}'< {\varepsilon}$ in the above construction.

Let $S(n)$ denote the space usage of our structure in bits. The top data structure can be implemented using e.g. [@KarpinskiN09] and requires $O((n/\log^3 n)\log^{2+{\varepsilon}})=o(n)$ bits. Dominance data structures use $O(n\log\log n)$ bits 