# 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] < 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.

• $X, S, E$ will vary from query to query, and there will be $\leq 1'000'000$ queries. – Andrej Karadzic Oct 9 '14 at 22:52
• What makes you think this invalidates my solution? Also, I don't see how the number of queries makes a difference, and indeed why you are bounding the size of the array and yet still using asymptotic notation. If $N \leq 10^6$ then there is an $O(1)$ solution without any preprocessing. – Yuval Filmus Oct 9 '14 at 22:55
• Could you please explain what you mean by sort in second step and how to use binary expansion of $E$ to find appropriate intervals? – Andrej Karadzic Oct 9 '14 at 23:16
• In the second step we treat each interval as an array (we copy it aside) and then sort it. Regarding the third step, you'll have to work it out yourself. I suggest you reindex the array as $a_0,\ldots,a_{2^k-1}$, and then consider some concrete values of $E$ and see how you would come up with the intervals. – Yuval Filmus Oct 9 '14 at 23:18
• Correct me if I am wrong, but I think that the second step is generating $N*N$ matrix? – Andrej Karadzic Oct 9 '14 at 23:22

As mentioned by Yuval, you just need to count how many elements in $a_1,\ldots,a_E$ are less than $X$.

I would recommend you to use persistent binary search trees, some lecture notes here and here. Briefly, you could build a binary search tree of $a_1,\ldots,a_N$ by inserting them to a empty tree one by one. By remember some information when you build the tree, you would be able to access the binary search tree of $a_1,\ldots,a_k$ for any $k$. This can be done in $O(N\log N)$ time.

Later when you find the root of the binary search tree of $a_1,\ldots,a_E$, which is stored in an array so accessing costs $O(1)$ time. Then you count how many nodes in the tree are less than $X$, which cost $O(\log N)$ time.

So you get $O(\log N)$ time per query and $O(N \log N)$ preprocess time! And it's also easy to implement.

• This is a beautiful use of persistent data structure! – Tsuyoshi Ito Oct 13 '14 at 6:09