i_m_joey's blog

By i_m_joey, history, 5 years ago, In English

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 ??

Read more »

  • Vote: I like it
  • -5
  • Vote: I do not like it