SPOJ D-Query/LightOJ-1188-Fast-Query Solution Approach Using Segment Tree

This is an interesting problem to solve using the Segment Tree. The complexity is like a standard segment tree.

So, Let’s begin the solution approach. Let an array with 8 elements (Like Light OJ),

To solve this, we should have a slight knowledge of Offline Query. So, what is an offline Query? Is it the hardest method? No! I know you know about Query. Right? Hmm. So, what is a query? A query is a search to you to give a solution. It may be a range or may not be a range (single element). So, a Query can be of two types. One and the most know is online Query, and another is Offline Query. An Online Query is that for which we reply or return value at the time of the query. And the other is we can store the queries and return the values as their sequence. So, is it the hardest to do? No, obviously!

So, if we mix the original array with the query, is it hardest to recognize which is an array and a query? No! How we mix!! Make the array element’s key and query right range the key of the query. And sort the mixed increasingly with their key. Now, you are ready to solve the problem. How!!

Let the query and array element be like Light OJ. (1188 — Fast Queries)

8 5
1 1 1 2 3 5 1 2
1 8
2 3
3 6
4 5
4 8

Which has 8 elements and 5 queries. Let’s make a for the mix.

Now, sort it increasingly as their Key but descending with their value. I think you can do that. Do it as your assignment.

Now, see the process,

When I get an array element, check if it was in before or not, right? You can use a map for that with constant time. If not, then its resultant value is 1, else 0. And when a query does a query for a range of queries (Left, Key). So, what is the benefit here of the offline query? When I value before to zero, it’s not needed up to the Key (Right). Look at the process below:

So, after all the updates and Query,

Happy Coding!!

Originally published at https://blog.habibrahman.me.