莫队是一个通过对指针移动进行优化来使得降低序列统计类问题复杂度的算法那么如果把莫队搬到树上……

普通莫队优化复杂度的最重要的诀窍是在大部分的询问中左指针的移动在一个块内,而右指针的移动遵循一定规律使得在左指针在同一个块内的时候,右指针能够以接近O(n)O(n)的复杂度统计完所有询问的信息。

基本思想在这,但是自己还是写不出来。多见见吧

发表评论

电子邮件地址不会被公开。 必填项已用*标注