根号数据结构

本文主要是介绍根号数据结构，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

根号数据结构

在以前，我十分讨厌带根号的数据结构，认为不够优雅.  

但是在很多时候，带 $\mathrm{log}$ 数据结构的作用比较局限，且复杂.  

这个时候，根号数据结构的作用是十分巨大的.   

根号数据结构主要依赖于复杂度的分析，即将看似暴力的做法捏合在一起.   

普通莫队

最简单的莫队.  

可以处理只有查询，没有修改的问题.  

每次先按照左端点所在块排序，若块相同则按照右端点排序.  

时间复杂度为 $O(q \sqrt n)$.  

bool cmp(query i, query j) {
    if(i.l / B == j.l / B) return i.r < j.r; 
    return i.l / B < j.l / B; 
}

没有什么其他强调的，但尽量不要在后面多加一个 $\log$, 否则复杂度就很难看.  

带修改莫队

这篇关于根号数据结构的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！