在线地支持单点加矩形求和，要求 O(\sqrt{n})-O(1) 或 O(1)-O(\sqrt{n})。
可以直接使用 $n^{\frac{1}{4}}$ 叉树套树维护。
注意叶子节点不需要开儿子数组，这样空间可以保证为 $O(n^\frac{3}{2})$，否则是 $O(n^\frac{7}{4})$。
$2.$ 特殊情况，保证 $O(1)$ 的那一部分涉及到的横坐标互不相同，纵坐标互不相同。
同样考虑 $n^{\frac{1}{4}}$ 叉树套树，但只分前两层，这一部分空间复杂度为 $O(n)$。
此时会出现两条宽为 $O(\sqrt{n})$ 的边角，利用给定的性质直接暴力即可。空间复杂度依然为 $O(n)$。
---
将 $>x$ 的数 $-x$。设所有数的值域为 $[1,V]$。
$1.$ $V$ 小。
- 如果当前 $mx\le 2x$，那么将 $(x,mx]$ 中的数减少 $x$。
- 如果当前 $mx>2x$，那么将 $[1,x]$ 中的数增加 $x$，然后打一个全局 $-x$ 的标记。
注意要将相同的数合并起来。
这样我们每次做的复杂度与 $mx$ 的减小量是一致的，因此总复杂度 $O(V)$。
$2.$ $V$ 大。
建立一棵平衡树，每次操作分裂为 $[1,x],(x,2x],(2x,V]$ 三部分。
第二部分暴力地一个一个插入到第一部分，第三部分打一个全局 $-x$ 标记然后合并到第一部分，这样可以保证合并时值域不交。
每个数一旦出现在第二部分，它的值至少会缩小 $2$ 倍，因此时间复杂度是 $O(n\log n\log V)$。
这两种结构单独使用可以维护每种值的出现情况。在外层套一个分块就可以维护区间信息。
$3.$ 区间信息，$V$ 大。
对于值域倍增分块，$[2^k,2^{k+1})$ 为一块。每一块开一棵线段树。
每次操作分别考虑每一块，如果 $x<2^k$ 那么就区间减，并暴力地修改所有 $[2^k,2^k+x)$ 的数，否则暴力地修改所有 $(x,2^{k+1})$ 中的数。
时间复杂度是均摊 $O(n\log n\log V)$。
值得注意的是其中倍增分块的思想，这样分块的好处是每一个数**一旦被暴力处理就一定会掉到下一块**，保证了均摊复杂度，而别的分块方式难以拥有这样的优势。
实际上，第三种方法可以说严格强于第二种方法。相比第一种方法，它在 $m$ 大，或能够快速支持区间减的问题上更占优势，在 $m$ 小的时候第一种方法会更占优势。
---
维护一个序列，支持末尾插入，删除，询问区间信息（例如询问一个区间的凸包上的切线）。
考虑一个原始的线段树结构。
如果没有删除操作，我们考虑在一个块插满的时候暴力建出其凸包，然后询问时直接将询问区间在线段树结构上分裂开，然后对于每一个分裂出的区间在其凸包上二分即可。
但如果有删除操作就会导致复杂度爆炸，因为很可能反复重构一个巨大的块。
我们对每一个没有插满的块打上标记，即询问时遇到这个块需要继续递归。特别地，将每一层最后一个插满的块也打上标记。
我们只对没有打标记的块建出凸包。插入时如果某个块被插满了那么就把它前面那个块的标记去掉，并且重构。删除时将包含当前删掉的位置的块全部打上标记。
对每一层进行势能分析可以得到修改的复杂度是均摊 $O(n\log^2 n)$ 的。而查询的复杂度依然是 $O(\log^2 n)$。修改查询都有两个 $\log$ 是因为凸包询问是 $O(n\log n)-O(\log n)$ 的。
---
单点修改，区间信息查询（含幺半群）。对于多个修改和查询的时间组合设计数据结构。
$T_m(n)$ 表示长度为 $n$ 的序列，查询的时间上限为 $m$，修改的最小时间。
把这个序列分成若干长度为 $B$ 的块，块内维护前后缀和。
如果查询区间至少经过了一个分块点，那么递归到 $T_{m-2}(\dfrac{n}{B})$ 的子问题。
否则递归到 $T_m(B)$ 的子问题。
修改时这两部分必须都要进行操作。
可以得出
$$T_1(n)=O(n^2)$$
$$T_2(n)=O(n)+2T_2(\dfrac{n}{2})$$
$$T_m(n)=O(B)+T_{m-2}(\dfrac{n}{B})+T_{m}(B)$$
dp 计算最优的 $B$ 即可。
---
给定一棵点有颜色的树，每次询问一棵子树，求出其中每种颜色的出现情况的 bitset。强制在线。
如果直接把子树看成 dfs 序上的区间，那么预处理的时间复杂度为 ST 表 $O(\dfrac{n^2\log\frac{n}{B}}{\omega B})$ 分治 $O(n\log\frac{n}{B})$，空间复杂度均为 $O(\dfrac{n^2\log\frac{n}{B}}{\omega B})$，单次询问复杂度是 $O(\dfrac{n}{\omega}+B)$。
这种做法比较简单，但是没有很好地利用子树的性质，而是直接把子树强化成了区间，导致空间复杂度以及时间常数较大。
这里提供一种更为厉害的做法。
我们希望标记一些点，使得对于每一个点 $u$ 都满足以下两个条件之一
- $size_u\le B
-
\exists v\in subtree_u\cap S,size_u\le size_v+B
其中 S 为被标记的点组成的集合。
设定 B 之后从下往上进行贪心，如果一个点不满足条件就标记它，这样一定可以求出标记的点数最少的方案。
但我们还需要理性理解一下为什么这样标记的点不会太多。
方便起见，把没有被标记的点称为白点，被标记的点称为黑点。
设 \phi_1 为所有真祖先都是白点的白点个数，\phi_2 为所有真祖先都是白点的黑点个数。
考虑最终状态中黑点组成的虚树。显然叶子节点的个数 x 不会超过 \dfrac{n}{B}。
按照贪心过程一步一步地进行标记，同时关注 \phi_1,\phi_2 的变化。
先标记这 x 个虚树上的叶子节点，此时 \phi_1\le n-xB,\phi_2=x。
接下来每一步标记，考虑两种情况
-
如果当前点在虚树上只有 1 个儿子，那么 \phi'_1\le \phi_1-B,\phi'_2=\phi_2
-
如果当前点在虚树上有 \ge 2 个儿子，那么 \phi'_1\le \phi_1,\phi'_2\le \phi'_2-1
最终状态 \phi'_1\ge 0,\phi'_2\ge 1。
因此最终的黑点个数最多为 \dfrac{n-xB}{B}+2x-1=\dfrac{n}{B}+x-1\le \dfrac{2n}{B}。
我们只需要暴力预处理所有黑点子树内的 bitset，每次询问直接暴力往上推即可。
预处理时间复杂度 O(\dfrac{n^2}{B})，空间复杂度 O(\dfrac{n^2}{\omega B})，单组询问时间复杂度 O(B)。
当然这种题一般最后还会有一些 bitset 之间的操作，因此询问的时间复杂度一般还会带一个 O(\dfrac{n}{\omega})。
可以发现，这种做法不仅降低了预处理的空间复杂度，还将询问的时间常数变为了原来的一半。虽然预处理时间复杂度略微变大，但是它一般不在瓶颈上，并不会影响这个做法的优越性。
两种树剖砍 \log 技巧。
直接把线段树改为全局平衡二叉树就可以砍掉 $1$ 个 $1\log$。
$2.$ 树剖套分块
直接做一般是 $O(n\sqrt{n\log n})$。考虑改一下分块方式，对于一条长度为 $len$ 的重链，它所代表的区间用 $O(\sqrt{len})$ 的块长进行分块。分析可以发现复杂度为 $O(\sum\sqrt{\dfrac{n}{2^k}})=O(\sqrt{n})$。
只不过很多情况下实际表现不一定比原来的做法要快就是了。。。
---
lxl 在 APIO 讲课中提到的一种数据结构技巧，这里用我自己的理解来写一下。
设 $x$ 个最多能将操作对象划分为 $F(x)$ 个等价类。
将 $m$ 个操作以 $B$ 为块长进行分块。
设当前块为 $[l,r]$，那么我们先求出 $n$ 个操作对象被 $[l,r]$ 中的操作划分出的 $F(r-l+1)$ 个等价类。
然后对这个块进行分治，设当前处理的区间为 $[l,r]$。
如果 $l=r$，那么当前只有 $2$ 个等价类。直接对需要操作的那个打上标记即可。
如果 $l<r$，那么求出当前 $F(r-l+1)$ 个等价类被 $[l,mid]$ 中的操作的划分出的 $F(mid-l+1)$ 个新等价类，相当于合并若干等价类。然后递归处理 $[l,mid]$ 即可。处理完之后需要撤销合并操作，因此我们可以用有根森林来表示等价类，加入一个点之后要对它进行 pushup，删除一个点之前要先对它进行 pushdown。对于 $(mid,r]$ 也可以类似处理。
这样分治的复杂度为 $T(n)=2T(n/2)+f(n)$。
整个过程的时间复杂度为 $\dfrac{(n+T(B))m}{B}$，取 $B$ 满足 $T(B)=O(n)$ 可以得到最优的复杂度。
例如操作对象为二维平面上的点，操作范围为半平面时，$F(n)=O(n^2),T(n)=O(n^2)$，取 $B=O(\sqrt{n})$ 可以得到最优时间复杂度为 $O(m\sqrt{n})$。
---
有一个序列 $a$，初始全为 $0$，给定序列上的若干个区间，要求支持以下两种操作：
- 给定 $x,w$，将 $a_x$ 修改为 $w$。保证 $w\ge 0$。
- 给定 $w$，删除所有权值 $\ge w$ 的区间。
在每次 $2$ 操作之后输出哪些区间被删除了。
对于一个区间，如果某个包含它的区间没有被删除，那么它肯定也不会被删除。称一个区间为好的当且仅当它没有被删除并且所有包含它的区间都已经被删除。
维护所有好区间，显然他们的左右端点都是单调递增的。每次修改操作影响到的一定是一段左端点的区间。在删除一个区间之后加入所有新产生的好区间即可。这些都可以用线段树维护，时间复杂度 $O(n\log n)$。
---
给定一个不带权无向图，保证每个点至多在 $k$ 个简单环中，多次询问两点间最短路。
随便找一棵生成树，对它进行点分治。
设当前根为 $rt$。因为题目保证每个点至多在 $c$ 个简单环中，所以 $rt$ 的不同子树之间至多有 $c$ 条边。
我们希望在 $rt$ 处处理所有以它为分治点的询问 $(u,v)$。显然 $(u,v)$ 间的任意一条路径不可能既不经过 $rt$ 又不经过这 $c$ 条边。
因此我们可以把 $rt$ 以及这 $c$ 条边所涉及到的 $O(c)$ 个点拿出来，以这些点为源点跑 bfs。询问 $(u,v)$ 的时候只需要在这 $O(c)$ 个点中枚举一个 $x$，求出 $\min\limits_x\{dst_{x,u}+dst_{x,v}\}$ 即可。
时间复杂度 $O(k((n+m)\log n+c))$。
---
给定一个序列 $a$，$m$ 次询问 $[l,r]$ 中选 $k$ 个不相交的子段的最大权值和。
可以发现，答案关于 $k$ 是上凸的。
建立一棵线段树，在线段树上的每一个节点 $[l,r]$ 中维护一个 $2\times 2$ 的矩阵，两维 $0/1$ 分别表示 $l$ 和 $r$ 是否被选择。矩阵中的每个元素是一个横向跨度为 $O(r-l)$ 的函数，其中第 $i$ 维的值表示从 $[l,r]$ 中恰好选择 $i$ 个两两无公共点的子段，并且满足两维 $0/1$ 的限制时的答案。根据之前的性质可以得到，矩阵中每个元素都是上凸函数。
这一部分可以通过归并排序在 $O(n\log n)$ 的时间复杂度内完成。
对于每次询问，先将询问区间 $[l,r]$ 分裂成线段树上的 $O(\log n)$ 个节点。但我们显然不能直接像预处理时一样直接合并每个节点的矩阵，否则时间复杂度会达到 $O(nm\log n)$。
考虑使用 wqs 二分，设当前二分的斜率为 $k$。在每个分裂出的节点中通过二分求出矩阵中每个元素上斜率为 $k$ 的切线，此时矩阵里的元素不再是一个函数，而是一个整数。最后将这些矩阵合并起来即可。时间复杂度降低到 $O(n\log n+m\log^2n\log V)$，其中 $V$ 是 wqs 二分的值域。
将对每个询问单独二分改为整体二分就可以进一步降低复杂度。具体来说，对于当前需要考虑的 $t$ 个询问，我们只考虑它们在线段树上分裂出的 $O(t\log n)$ 个节点，在这些节点上暴力找出切点。递归处理左侧部分时，只需要保留凸函数上在当前切点右侧的部分。
时间复杂度分析：将整体二分的过程看作一棵二叉树，对于线段树上的每一个节点 $[l,r]$，它在二叉树的同一层节点上产生的时间代价不超过 $O(r-l)$，而线段树上所有节点的长度总和不超过 $O(n\log n)$。因此时间复杂度为 $O((n+m)\log n\log V)$。
---
定义一种信息，每个信息有一个大小 $size$，设 $z=x\times y$，那么 $z$ 满足 $size_z=size_x+size_y$，这个操作的时间复杂度为 $O(size_z)$。信息之间的合并不满足交换律但满足结合律。
给定一棵以 $1$ 为根的树，每个节点 $u$ 上有一个信息 $a_u$。设 $b_u=a_u\times\prod\limits_{v\in son_u} b_v$。求出 $b_1$。
先进行重链剖分，我们只对每个轻儿子 $u$ 计算 $b_u$。
容易发现这样所有需要计算答案的 $size$ 总和是 $O(n\log n)$ 的。
假设当前计算的是 $b_u$，那么先把 $u$ 的轻儿子的 $b$ 分治合并起来。按照子树大小带权地分治即可做到 $O(n\log n)$。
然后我们对以 $u$ 为顶的重链进行分治，将重链两侧轻儿子的信息合并起来。同样按照子树大小带权地分治即可做到 $O(n\log n)$。
---
有 $n$ 个点，共进行 $m$ 次操作，每次操作给定 $l_1,l_2,x$，并对于 $\forall i\in [0,x)$ 连边 $(l_1+i,l_2+i)$。在线维护连通性。
考虑对每个 $k$ 维护一个关于所有长度为 $2^k$ 的区间的并查集。称其为“第 $k$ 层并查集”。
我们相当于要正确维护第 $0$ 层并查集。
对于一次操作，我们可以将它拆成不超过两次 $x=2^k$ 的操作。
对于一个 $x=2^k$ 的操作，我们先在第 $k$ 层并查集中将 $l_1,l_2$ 合并。
如果 $l_1,l_2$ 本来就在同一连通块中，说明本次操作不会产生任何影响。
否则我们递归到第 $2^{k-1}$ 层并查集中将 $l_1,l_2$ 以及 $l_1+2^{k-1},l_2+2^{k-1}$ 分别合并即可。
可以发现这样做的时间复杂度只与有效合并次数相关。而因为一共有 $O(\log n)$ 层，每层 $O(n)$ 个点，所以有效合并次数是 $O(n\log n)$ 的。
因此总时间复杂度为 $O(n\log n\alpha(n)+m)$。
---
维护一个 $n\times n$ 的 $01$ 矩阵，在线地支持单点修改，实时维护同色极大四连通块个数。
考虑维护一棵类似于线段树的结构，每次将当前矩阵分为两部分。
在每个节点处维护这个节点对应子矩阵的边界上所有点在这个子矩阵中的连通性（即一种染色方案使得两个点颜色相同当且仅当它们在同一个连通块中），以及只考虑这个子矩阵时的连通块个数。
合并时需要处理两个矩形边界处的连边，暴力地建图 dfs 即可，对连通块个数的贡献也是容易计算的。设当前矩形周长为 $len$，则合并的复杂度为 $O(len)$。
如果我们每次都按照行划分，则进行一次修改的时间复杂度为 $O(n\log n)$。
我们也可以每次按照行列中较长的一个划分。则进行一次修改的时间复杂度为 $O(n)$。
总时间复杂度为 $O(n^2+nm)$，其中 $m$ 为操作次数。