这题不愧“下金蛋的母鸡”，解法确实多种多样，下面我就来总结一下这题的各种算法。
莫队算法
- 两种实现：
- 数组（“后缀和”），复杂度\(O(n\sqrt{n})\)
- BIT维护前缀和，复杂度\(O(n\sqrt{n}\log_2{n})\)
- 是最容易想到的算法，且实现简单效率高
启发式合并（非平衡树）
- 可用数组、map、vector等实现，复杂度\(O(n\log_2{n})\)
- 代码最短，但实现不好可能会TLE
启发式合并（平衡树）
- 用Treap即可
- 复杂度\(O(n\log_2^2{n})\)
- 容易想到，但实现复杂，且容易TLE
树分治
- 复杂度从\(O(n\log_2{n})\)到\(O(n\log_2^2{n})\)不等，取决于实现
- 用的人较少，在思维难度、代码难度和效率上均不占明显优势
其他
- 大点预处理小点暴力形分块
- 带合并的哈希表+LCA
- 其他某些奇怪的离线处理树上询问的方式（奇怪排序、二分、LCA等等）
- 以上算法均不如前三种算法（至少给定的程序中以上算法没有人AC）
注意事项及总结
- 对于其中很多种方法，只要把BIT维护前缀和改为纯数组维护“后缀和”就可以去掉一个\(\log_2{n}\)，效率提升不少（虽然BIT常数很小）
- 不要盲目运用平衡树等数据结构，往往存在着更为简单好写的做法