# Elements in a less than a value in a subarray

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.

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

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.