×

# [closed] What is offline query?

 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? asked 23 Sep '15, 08:32 893●2●11●34 accept rate: 10%

### The question has been closed for the following reason "The question is answered, right answer was accepted" by dragonemperor 27 Sep '15, 13:29

 8 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. :-P 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...) answered 23 Sep '15, 09:10 4★gkcs 2.6k●1●11●27 accept rate: 9% 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? (23 Sep '15, 11:40)

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×69

question asked: 23 Sep '15, 08:32

question was seen: 2,594 times

last updated: 16 Mar '17, 10:13