hippie's blog

Square Root Decomposition of Queries
By hippie, 10 years ago, In English

How exactly is the square root decomposition of queries (also sometimes referred to as Mo's Algorithm), used for offline processing of queries? If possible, please explain with an example.

NOTE :- I've gone over this post, but it lacks in covering the topic with an example and complexity analysis properly.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

I think it might be easier to understand if I explain with an actual solution of a problem. The problem is this one and the solution is as follows.

  • Split the k queries in buckets of size .
  • Mark all the countries (marked countries are those for which we still haven't found the answer).
  • Process all the queries in each bucket at once. To process all queries, we use delta encoding to be able to do that in O(m). Check, for every unmarked country, whether after all the queries in this bucket the number of meteors it possesses is at least the desires amount pi. If it is, check all the showers in order until the condition is satisfied. Mark the country to avoid processing it in future buckets.
  • Complexity analysis: We have buckets and each bucket is processed in O(m), so complexity of this part is . Now, for the part of checking all queries in the bucket to see the first one that gives a certain country the desired amount of meteors, we must do it efficiently. To do so, we must have a list of the sectors this country owns and check for each shower if this sector receives meteors or not. Since every sector is owned by only one country and we process a country only in one bucket (which has no more than showers), this part will also have complexity . So, the complexity of the algorithm is, indeed, .

SQRT-decomposition is a concept that's very hard to understand, at least for me. I hope I was clear enough.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

This is also a very good tutorial on Mo's algorithm.

http://blog.anudeep2011.com/mos-algorithm/

→ Reply