值域分块
Q
给定一个序列，实现单点修改 \(O(1)\)，以及区间查询 \(O(\sqrt n)\)
A
考虑设 \(block_i\) 表示块 \(i\) 的和，那么修改便是 \(O(1)\)
全局查询时，整块调用 \(block\)，散块暴力即可\(O(\sqrt n)\)
还有一些常见的例子，比如配合莫队代替主席树（区间mex）
莫队二次离线
普通莫队本来就要离线询问，然后通过左右端点的移动，变成我们可以直接处理的 \(n\sqrt m\) 次询问。但有时这些询问的单次复杂度为 \(O(\log n)\)
那么莫二离就是把 \(n\sqrt m\) 次询问再次离线下来，如果题目有比较好的性质（可以差分），我们就能用值域分块同样 \(O(n\sqrt m)\) 处理全部询问
P4887 【模板】莫队二次离线（第十四分块(前体)）
给了你一个序列 \(a\)，每次查询给一个区间 \([l,r]\)，查询 \(l\le i<j\le r\)，且 \(a_i\bigoplus a_j\) 的二进制表示下有 \(k\) 个 \(1\) 的二元组 \((i,j)\) 的个数。
P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II
给你一个长为 \(n\) 的序列 \(a\)，\(m\) 次询问，每次查询一个区间的逆序对数。
我们考虑直接用莫队做，那么就出现了 \(n\sqrt m\) 个形如 \(\sum_{i\in[l,r)}[a_i>a_r]\) 或 \(\sum_{i\in(l,r]}[a_i<a_l]\) 的询问
两个本质等价，我们考虑第一种，发现可以差分
\(\sum_{i\in[1,r)}[a_i>a_r]-\sum_{i\in[1,l)}[a_i>a_r]\)
我们发现前面一项我们可以统一预处理，于是我们就剩 \(n\sqrt m\) 个形如 \(\sum_{i\in[1,p)}[a_i>x]\)
然后我们按 \(p\) 排序，就变成了只有 \(O(n)\) 次修改，\(O(n\sqrt m)\) 次查询
用值域分块可以很好解决
标签：分块,值域,sum,离线,sqrt,莫队 From： https://www.cnblogs.com/zhy114514/p/18258895