What is offline query?

general
1

While trying to solve http://www.spoj.com/problems/DQUERY/en/, I came across an offline solution. It sorted the queries before hand and solved it. Can anyone help me understand the approach? How can storing the queries beforehand solve the problem?

1 Like
2

EDIT:
Here is a video editorial on Mo’s algorithm. It uses offline query processing with SPOJ - DQUERY problem as a working example.

Mo’s Algorithm - DQUERY

This problem belongs to the class of problems:

  1. Here is a set of elements to be queried.

  2. Here are the queries.

  3. Mamu! Give me red. :stuck_out_tongue:

An offline algorithm allows us to manipulate the data to be queried, before any answer is printed. This is usually only possible when the queries do not update the original element set. So we have the option of completing step 1, and doing some processing on the elements. This processing should enable us to answer any subsequent query very efficiently.

Then we go to step 2, where we print the pre-computed answers or use the processing after step 1 to get the answers quickly. Finally, print each answer.

As an example, try to find the number of inversions for any given range (l,r) in an array where 1<=l<=r<=n. Then try to do this for k queries. You will find the offline solution to be efficient.

Also, note how the processing after step 1 is similar to preprocessing is general questions (Finding primary numbers from 1 to n before checking for primality, etc…)

8 Likes
3

Thank you. This helps. But I failed to solve my first offline query problem. I have posted that as another query. Can you take a look at that please?