mnbvmar's blog

By mnbvmar, 2 years ago, In English,

Hey, CF community!

I have a newbie question about the square-root decomposition method on arrays. You probably know the trick — assume we have to do a sequence of queries on the array of size n. We divide it into pieces of size . Then when any query (do something on interval) comes up, there are pieces covered by the interval (which we can somehow process quickly) and elements outside these pieces (which we can brute-force). Thus we arrive into something like or per query.

Now my question comes — many people here name such a technique; its name is Mo's algorithm. However, my searches in Google and arXiv gave no information on the origins of the name. However, it seems to be widely used on Codeforces and we-love-algorithms-blogs. I'm quite interested in:

  1. Who was the first to use this name for the technique? When was it?
  2. Which Mo (I guess many of them contribute to computer science, at least arXiv says so) does the name refer to?

Thanks in advance for your answers.

A funny sidenote: I had also another question in my mind before — it was about BITs (binary indexed trees). I thought that it must be connected with bit manipulations. It got really weird when people kept discussing about Fenwick trees there. I was explaining to myself that we use bit operations to move in the tree more efficiently. It took me like a year to realize how stupid I had been... :D

Read more »

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