0
$\begingroup$

Let A be an fixed array of size n. Q(i,j,k) is number of elements from A[i] to A[j] which are less than k.

Currently I am using segment tree with each node containing sorted array of leaf elements. This answers the query in O((log n)^2) with O(n*log n) space and per-processing.

Is there a way to answer this in O(log n) while keeping the per-processing and space complexity same.

$\endgroup$
  • $\begingroup$ What operations do you need to do on the data? Update the values at arbitrary array indices? Or is the data fixed and unchanging? $\endgroup$ – D.W. Oct 11 '14 at 7:19
1
$\begingroup$

This is essentially the 2D orthogonal range counting problem from computational geometry, which has attracted a lot of attention over the years. Fractional cascading definitely could be applied to reduce the query time to logarithmic while preserving the other big-O bounds. In a nutshell, the idea is to make auxiliary data structures that relate the positions of elements in each parent array to positions in the child array, so that, given the results of a search in the parent, searching the child for the same key is constant-time.

$\endgroup$
0
$\begingroup$

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$

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.