### Zeardoe's blog

By Zeardoe, history, 4 weeks ago,

In Chinese CSP-S1 today morning, there was a question to use "The Method of Four Russians" to solve RMQ problem. Can anyone do me a favor to teach me what it is? Thank you!

• +15

 » 4 weeks ago, # |   +15 You don't need to learn it now.CCF just had water in it's mind.Don't pay too much attention on that F*** problem
•  » » 4 weeks ago, # ^ |   +16 Haha. But the contest is good, I think. I've found that even in Codeforces this Russian website there are few explanations about TMoFR.
 » 4 weeks ago, # |   +16
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +8 And CCF says this algorithm is $\Theta(N+Q)$ , but OI-wiki says that it should be $\Theta(N\log\log N+Q)$ ! I think CCF is wrong.UPD:I didn't see clearly. It should be $\Theta(N+Q)$
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +4 That's a $+1/-1$ RMQ problem because the depths of adjacent nodes in the euler sequence only can be differ by one. So this algorithm is $\Theta (N+Q)$.
•  » » » » 4 weeks ago, # ^ |   +8 Oh yes I didn't see that clearly.Sorry!
•  » » 4 weeks ago, # ^ |   -7 Great, is this blog from you? That's nice.
•  » » » 4 weeks ago, # ^ |   +8 Nope,but OI-wiki.
 » 4 weeks ago, # |   +10 In a word, I think it's quite not proper to put an Russian alorgithm in a Chinese exam :DMaybe "The Method of some numbers of Chinese" should be put in.
 » 4 weeks ago, # |   0 One of the things you DON'T need to know.
•  » » 4 weeks ago, # ^ |   0 Sure. I even don't know what the Cartesian tree is about.
 » 4 weeks ago, # |   +19 The Method of Four Russians is a very general technnique, and not just limited to the RMQ. It roughly has to do with "precomputing" the answers for small parts of the problems, and use some other more general structure for the larger parts of the problem.For instance, in RMQ with The Method of Four Russians, you essentially try to make a sparse table on the range-minima of blocks of small size, and precompute the answers for all small blocks. However, just doing a brute force doesn't work for all small blocks, so rather than solving this for the original problem, we try to find the position of the minimum in equivalence classes of small blocks (which are $C_s$ in number, where $s$ is the size of blocks, and $C_s$ is the $s$-th Catalan number), which are few in number, and recognize which block each small array corresponds to.For a more detailed explanation, you can consider reading https://web.stanford.edu/class/cs166/lectures/01/Small01.pdf