Please explain the following problem using Segment tree.
I know that we store sorted elements in each node, but the problem is how to the query part.
Thanks in advance. If possible please share a Java solution using Segment tree.
Please explain the following problem using Segment tree.
I know that we store sorted elements in each node, but the problem is how to the query part.
Thanks in advance. If possible please share a Java solution using Segment tree.
I will try to explain my solution which uses a segment tree.
First of all, i use the segment tree as follows:
Code snippet: segment tree.
As you can see, nothing special here. These are standard operations on a segment tree. Note that initially all elements of the tree are zeroes.
Let’s get back to the actual problem. I iterate over the input array a few times to find all the groups/blocks of same numbers. For example [1,1,2,3,3,3,3] has 3 groups which are [ 1,1 ], 2 and [ 3,3,3,3 ]. In particular i want to know 3 things for each element:
Here is how my 3 new arrays will look like for the sample input array:
Note: all arrays are 0-indexed
[1,1,2,3,3,3,3] - original array
[2,2,1,4,4,4,4] - groupSize array
[0,0,2,3,3,3,3] - start array
[1,1,2,6,6,6,6] - end array
Actually for the array groupSize, it is enough to keep the size of the group at the start index of the group. So my actual groupSize array looks like:
[2,0,1,4,0,0,0]
Now there are 3 types of queries we need to consider:
Now, we have reduced the problem to deal only with whole groups, i.e. every query will cover only whole groups.
Since a query (L,R,K) asks for only groups of size K and larger, this query doesn’t care about groups of size less than K (mr. obvious :D). Now, the key idea is to sort the queries and groups together in a single array as ‘events’. An event will have a variable called value . For queries, value = K and for groups value = groupSize for that group. We sort the events in descending order of their value (from largest to smallest).
Now, Iterate the list of events from largest to smallest and:
The sorting we did ensures that for a query (L,R,K) we only get results for values >= K.
Not that for each event you need to keep some information like:
Full code: solution in c++
Edit (cleaned up code): cleaner solution
I hope i explained it well enough so that you can try and code it yourself. Once you have solved a problem like this it will become much easier to recognize and solve it next time. Hope it helps. Cheers!
I have written binary search approach solution for this question.
Will you please point out the mistake i have done in my code.
Here is the link of my code Ubuntu Pastebin
Perhaps if you try to explain how your solution works i might understand. I cant just look at that big chunk of code and understand how it works. It’s almost like reading your mind :).
Ya you are correct. I have commented about the logic of the code. Please check if that helps. I just can’t figure out the mistake. Oh god.