【数据结构】根号系列 2 —— 莫队算法入门
前言
莫队,是由来自国家集训队的莫涛,发明的算法。
本质上,莫队是分块的一个子集,但由于分块本身应用场景复杂(可以解决较复杂的树上、图上问题,或者是非常难的序列问题)
这也导致莫队算法的应用变化多样,不同问题的难度差距巨大。
本文难度与上一篇相比,提升较大,且需要读者掌握序列分块、值域分块,如果觉得有难度,可以跳过这一篇。
本文只介绍最简单的普通莫队,不涉及带修莫队、回滚莫队,树上莫队,莫队二次离线等算法。
引入 - 1
举个简单的 例子:
给你一个长度为 n 的序列,有 q 次询问,每次询问一个区间 [l,r]...