2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $X, S, E$ will vary from query to query, and there will be $\leq 1'000'000$ queries. $\endgroup$ – Andrej Karadzic Oct 9 '14 at 22:52
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 9 '14 at 22:55
  • $\begingroup$ Could you please explain what you mean by sort in second step and how to use binary expansion of $E$ to find appropriate intervals? $\endgroup$ – Andrej Karadzic Oct 9 '14 at 23:16
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 9 '14 at 23:18
  • $\begingroup$ Correct me if I am wrong, but I think that the second step is generating $N*N$ matrix? $\endgroup$ – Andrej Karadzic Oct 9 '14 at 23:22
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.