# Analysis of finding the k-th largest element in a subsegment of an array

Given an array $A$ of length $N$. There are $Q$ queries, each queries will be in the form

What would be the c-th number in the segment A[l...r] if the array is sorted?


I've come up with an $\mathcal{O}(N\log N+Q\log^3N)$ solution:

Build a segment tree, keeping array A sorted in each subsegment.
Binary search the value v which will be the answer.
Each time we binary search, we query the segment tree:
"What will be the rank of v in the subsegment A[l...r]"


Each segment tree queries takes $\mathcal{O}(\log^2N)$ time:
$\mathcal{O}(\log N)$ time for segment tree traversal and $\mathcal{O}(\log N)$ time for binary search the rank of value in the segment.
For each segment tree queries, if the we have to call query in both left node and right node, then we have to sum up the queries.

C++ code:

int query(int currentNode, int Left, int Right, int v){
if(LeftBound[currentNode] == Left && RightBound[currentNode] == Right){
return lower_bound(segmentDataVector[currentNode].begin(),segmentDataVector[currentNode].end(),v) - segmentDataVector[currentNode].begin();
}
int half = (LeftBound[currentNode] + RightBound[currentNode])/2;
// For simplicity, left node number will be 2*currentNode and right node number will be 2*currentNode + 1.
if(Left <= half && half < Right){
// Query again in both left node and right node.
return query(2*currentNode, Left, half, v) + query(2*currentNode + 1, half + 1, Right, v);
}else if(Right <= half){
// Query only left node.
return query(2*currentNode, Left, Right, v);
}else{
// Query only right node.
return query(2*currentNode+1, Left, Right, v);
}
}


And we binary search for v which query(1,1,N,v) == r-l+1-c becomes true, answering v.

After that, I came up with a better solution which takes $\mathcal{O}(N\log N + Q\log^2N)$:

Build a persistent segment tree.
Count the array A into buckets B (like counting sort).
Let B[i] be an array denoting the occurrences of i in A.
Sort the array A into array C.
Create an array D of length N, setting all elements to zero.
Let the persistent segment tree be linked with the array D.
For i in C start from minimum to maximum:
For j in B[i]:
D[j] = 1
Update D[j] = 1 into current version of segment tree.
Binary search the version value v which persistent segment tree version v sums from l to r results c.
Answer B[v].


But it isn't optimized enough. I know there exists the $\mathcal{O}(N\log N + Q\log N)$ solution, but I didn't know the solution yet. My friend told me that he knows 3 solutions that are linearithmic. Please don't tell me the solution, I want to think a little bit more.

The question I want to ask is:

"Does an $\mathcal{O}(N\log N + Q)$ solution exists, regardless of memory complexity?"
If that really exists, please give me some clue/solution.

This problem is a classical problem which can be found in Codeforces(http://codeforces.com/blog/entry/9204), SPOJ MKTHNUM (http://www.spoj.com/problems/MKTHNUM/) and the anudeep's blog explanation which I don't want to read the solution yet(https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/)

• What's the context in which you encountered this problem? Can you credit the original source? How do you know there exists a $O(N \log N + Q \log N)$ time solution? – D.W. Jan 29 '18 at 1:34
• I've edited the statement, and the time complexity I've stated, I known from anudeep's blog and one of my friend. – S. Plum P. Jan 29 '18 at 6:22
• Thanks! Now I'm confused. You know of a blog post that might describe a solution but you don't want to read it? You don't want to read the solution yet but you're asking here for the solution? – D.W. Jan 29 '18 at 6:28
• No. I'm just asking whether there exists an $O(N\log N + Q)$ solution, but for the $O(N\log N + Q\log N)$, I want to think on my own for some time. Sorry for being unclear. – S. Plum P. Jan 29 '18 at 7:26