Finding the $k$th largest element in an evolving query data structure

Question

Basically, the problem I am solving is this. Initially, the array $A$ is empty. Then I am given data to fill the array and at any time I have to make a query to print the $|A|/3$-th largest element inserted so far.

I was solving the problem with segment trees, but I am not able to make a little modification to the query function of the segment tree. The query function that I wrote returns the largest element between indices $a_{\text{begin}}$ and $a_{\text{end}}$:

int query(int Nodenumber,int t_begin,int t_end,int a_begin,int a_end)
{
 if (t_begin>=a_begin && t_end<=a_end)
 return Tree[Nodenumber];
 else
 {
 int mid=((t_begin+t_end)/2);
 int res = -1;
 if (mid>=a_begin && t_begin<=a_end)
 res = max(res,query(2*Nodenumber,t_begin,mid,a_begin,a_end));
 if (t_end>=a_begin && mid+1<=a_end)
 res = max(res,query(2*Nodenumber+1,mid+1,t_end,a_begin,a_end));
 return res;
 }
} 

Note to make a query, I call the query function as query(1,0,N-1,QA,QB).

But I want to return the $|A|/3$-th largest element between indices $a_{\text{begin}}$ and $a_{\text{end}}$. So how should I modify the function to do this?

So updating, queries, updating, queries, updating, queries and so on are done randomly and several (upto 10ドル^5$) times.

So, for solving the problem, did I pick the right data structure? I thought of using heaps, but that will be too slow, as I would have to pop $|A|/3$ elements from the top and reinsert them for every query.

• Raphael: Welcome! Wow, that was barely legible. I edited to clarify the question; please check that I did not change the meaning.

Answer 1

Have a look at the Wikipedia page for segment trees:

It is, in principle, a static structure; that is, its content cannot be modified once the structure is built.

So it does not seem to be a good data structure for your scenario at all.

Note that the kind of query you want to perform is called selection (unimaginative, I know). Check the linked article for loads of algorithms. One simple way to solve your problem is this:

• Store elements in a sorted list. That means, updates (that is insertions) take linear time.
• For the queries, run a selection algorithm on the specified interval.

This approach can be improved by extending the list to a skip list.

Another approach is using binary search trees. If you use a self-balancing variant, that makes updates possible in $O(\log n)$ time. The queries you want can be implemented by storing in every node how many descendants it has, so we can find the $k$-th largest element in $O(\log n)$ time.

• Chopra Jack: :: Well I dont think the First one Selection algo will work.If there are N queries ,then I have to call Selection Algorithm N times, so overall worst case complexity will be O(N^2),as the time complexity for Selection Algorithm will is O(N).So can u please explain the idea of self-balancing in detail . Is there any stl in c++ for constructing Self Balancing Binary tree. Thanks!
• Raphael: @ChopraJack: Oh, it will work. You have not given runtime constraints in your question; do you have any? To be "precise", the total runtime will be $O(n(n+N))$ -- $n$ elements have to be inserted and $N$ queries are performed. Regarding self-balancing trees, please read the linked Wikipedia article and follow the links to implementations there. If you have problems with that material, you can ask a new question here. I'm afraid C++ libraries are off-topic here (and I really have no idea).

Answer 2

You can use a segment tree to perform dynamic selection in $O(\log S)$ per oper; where $S$ is the size of the universe. To do this, you need to maintain the total number of elements in the segment represented by a node.

In fact, a binary indexed tree can also be used. Or you could also use a balanced binary search tree as Raphael suggested.

Answer 3

It is worth to mention that the problem is solvable with two heaps. You have to maintain a max heap for the first ~2[A]/3 element and a min heap for the last ~[A]/3 element. Inserting is O(log[A]), query is O(1).

• CodeYogi: Please provide an example.