sqrt decomposition of input queries

Revision en1, by i_m_joey, 2016-08-19 08:33:53

I read about sqrt decomposition data structure on this site http://e-maxx.ru/algo/sqrt_decomposition (this site is in russian but google translate works pretty well) I have understood the standard algo of this DS in which we divide the input array into buckets of size sqrt(N) where N is the size of the array.

But here's what I cant understand:**sqrt decomposition of the input queries.**

Suppose that we have some problem in which we are given some input data, and then k queries, each of which we have to process and issue a response. We consider the case when requests are as requested (do not change the state of the system, but only asks for some information) and modifying (ie affecting the state of the system is initially set to the input data).

This is the given approach which I cant understand:split the k queries in buckets of size sqrt(k) and process all the queries in each bucket at once.

Why we decompose queries into sqrt size buckets ?? and how we can process all the queries in each bucket ??

Tags #data structure, sqrt-decomposition, emaxx

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English i_m_joey 2016-08-19 08:33:53 1060 Initial revision (published)