Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
