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:
- find sum of a range [a,b] in some array A
- update (increment) a single element in array A.
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:
- the group size i.e. the number of elements of the group it belongs to
- start index of group
- end index of group
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:
- A query (L,R,K) that falls in a single group. This happens when start[L] == start[R] AND end[L] == end[R]
- then the answer is 1 if R-L+1 >= K, otherwise 0.
- A query (L,R,K) that falls in two groups. This happens when end[L]+1 == start[R].
- then the answer is similarly calculated as in 1) but we consider the 2 groups.
- A query(L,R,K) that falls in three or more intervals. This happens if 1) and 2) did not happen. You can notice that the query interval will not always cover whole groups, i.e. it may ‘cut’ a group. This may only happen at most 2 times, on the edges of the query interval. These ‘cut’ groups will make our job with the segment tree later difficult, so we want to get rid of them. How do we do that? Well, we know where each elements’ group starts and ends, so we simply shorten the query interval to exclude ‘cut’ groups and add 0,1 or 2 to the result for that particular query if the sizes of the ‘cut’ groups exceed K.
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:
- if we encounter a group event, we update the segment tree at the start of the group
- if we encounter a query event, we query the segment tree on the query interval.
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:
- event type (query or group)
- L and R (for query type of events)
- order number (i called it position) of query, so that you can print the results in order at the end.
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! 
1 Like
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
1 Like
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 :).
2 Likes
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.