Count points in 2-d range You are given an array $A$ of size N $(N\leq 1\,000\,000)$ containing all integers $1..N$ exactly once. You are required to answer query in $O(\log^2 N )$ and to preprocess in $O(N\log^2N)$:


  How many elements are there between indexes S and E, that are less than X? $( |L| : \forall l \in L \leftrightarrow A[l] &lt; X  \bigwedge S\leq l \leq E )$


$X, S, E$ will vary from query to query, and there will be at most $1\,000\,000$ queries.

I found a lot of algorithms based on kd-trees, but they have complexity linear in the size of the output. Are there any other options, maybe using the property that X and Y coordinates are unique?
First, notice that it is enough to compute how many elements in $a_1,\ldots,a_E$ are less than $X$. (Why?)

Second, assume for simplicity that $N$ is a power of 2. We partition $\{1,\ldots,N\}$ into intervals in $\log N$ ways: as a single interval of length $N$, two intervals of length $N/2$, four intervals of length $N/4$, and so on. We sort each of these. This takes time $O(N\log^2 N)$. (Why?)

Third, given $E$ and $X$, write $a_1,\ldots,a_E$ as a sum of $O(\log N)$ intervals  of the kind we sorted above (use the binary expansion of $E-1$). Find the correct count for each of them in time $O(\log N)$ by searching for $X$ in the sorted interval, and compute the sum.