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.