n/\log\log n)$ nodes and spend $\Omega(\log \log n)$ time in every node. For this reason all previous methods need $\Omega(\log n)$ time.

Again, in this paper we achieve better query time by using $t$-shallow cuttings. Our solution is based on embedding a high-degree tree $T_0$ into the range tree $T$ and storing $t$-shallow cuttings in the nodes of $T_0$. These $t$-shallow cuttings provide us with additional information and enable us to spend $o(\log \log n)$ time in every visited node of $T$ when a query is answered. In order to achieve the optimal query time, we use a sequence of embedded trees $T_0$, $T_1$, $\ldots$ with decreasing node degrees.

Throughout this paper $n$ will denote the total number of points in a data structure. The number of points in a sub-structure of a global structure will be sometimes denoted by $m$. We assume w.l.o.g. that all point coordinates are positive integers bounded by $n$ and all points have different coordinates. The general case can be reduced to this case by applying the reduction to rank space technique. Our results are valid in the standard RAM model. In this model we assume that the word size is $\Theta(\log n)$ and that 