sqrt tree 瞎写——以 RMQ 为例
感觉猫树白学了
本文纯个人理解 + 口胡，如果有什么问题请往死里喷我
我决定从期望 $O(1)$ RMQ 开始说，考虑先对序列分块，块长 $O(\sqrt{n})$ ，然后维护块内前后缀信息和每两个块之间的信息
但是期望 $O(1)$ RMQ 不是有个缺点？
同块的时候是不是会退化成 $O(\sqrt{n})$ ？
那万一有别有用心的人来卡你怎么办？
我们发现我们其实还是在做一段更小区间的 RMQ
因此然后考虑我们 RMQ 是怎么做的
我决定从期望 $O(1)$ RMQ 开始说，考虑先对序列分块，块长 $O(\sqrt{\sqrt{n} })$ ，然后维护块内前后缀信息和每两个块之间的信息
但是期望 $O(1)$ RMQ 不是有个缺点？
同块的时候是不是会退化成 $O(\sqrt{\sqrt{n} })$ ？
那万一有别有用心的人来卡你怎么办？
我们发现我们其实还是在做一段更小区间的 RMQ
因此然后考虑我们 RMQ 是怎么做的
……
然后当序列长度足够小没必要分块的时候，就可以 $O(1)$ 查询的
于是我们得到了一个树形结构，这就是 sqrt tree
首先发现这东西层数 $O(\log \log n)$
因此明确其建树是 $O(n\log \log n)$ 的
考虑这里如果直接查询要扫 $O(\log \log n)$ 层直到一个可以 $O(1)$ 的区间
虽然还是期望 $O(1)$ 的（（
但是确实可以被卡到 $O(\log \log n)$ 不是吗（（
想想隔壁猫树是不是也遇到过类似的问题？
可以类似解决吗？
我们照样给它整成 $2^k$ 的形式然后试试能不能二进制
说人话就是所有块长都是 $2^k$ 的形式
那么显然块数也是 $2^k$ 的形式了
不难发现可以用位运算优化这个过程了，具体实现和猫树差不多，留给读者自行思考
不过我个人感觉这里倍增啊二分啊什么的都已经是 $O(\log \log \log n)$ 的了，基本上可以忽略不计了，至于吗（恼
考虑修改
隔壁猫树修改比直接重构优秀，看看 sqrt tree 行不行
朴素修改的话显然我们每一层都得重构一个结点，是 $O(n+\sqrt{n}+\sqrt{\sqrt{n}}+\dots)=O(n)$ 的
这不行啊，这怎么能给我们带来笑容呢
此时我们惊讶的发现，我们在原序列上的整块上做的居然也是 RMQ
于是我们再对于整块开一个 sqrt tree ，而不开什么块间的数组了
这样一来复杂度就是 $O(\sqrt{n}+\sqrt{\sqrt{n}}+\dots)=O(\sqrt{n})$ 单次修改了
区间修改有两种实现方法
第一种实现是考虑我们区间修改每一层是两个散块，那么就对这 $O(1)$ 个散块暴力重构，复杂度就会多一个 $O(\log \log n)$
第二种实现是给被完整修改的结点全部打上标记，那么修改复杂度不变，查询复杂度由于要查询祖先，就多了一个 $O(\log \log n)$
看了一下 OI-wiki 上的代码实现，感觉挺阴间的
口胡了一下可能可以用 ￥gg 论文里面 vEB 树的那种嵌套写法，可能会比 OI-wiki 上的好一些
感觉实战中肯定没什么用，正常人谁闲得无聊写这玩意儿啊