树链剖分能够将一棵树按照某种法则剖分为若干条链，从而便于维护树上路径的信息。 按照剖出链的法则不同，其性质也不同，大体可将树剖分成重链剖分，长链剖分和用于 Link-Cut Tree 的剖分（实链剖分）。 其中重链剖分用途最广泛，本文也只介绍重链剖分。 重链剖分 定义与部分性质 给出如下定义 重儿子。对于一个非叶子节点，其重儿子为其以它的所有儿子为…
线段树上二分 用形式化的语言讲，线段树上二分求解的是这一类问题。 给定 $L$，找到一个 $R \in [L,n]$ 满足$$f \Big( op\big([L,R-1]\big) \Big) = 1$$$$f\Big( op\big(R\big) \Big)=0$$ 其中 $f$ 为某种合法性函数，$op$ 是将区间信息合并为 $f$ 能处理的信…
中国剩余定理（CRT） 由于扩展中国剩余定理和中国剩余定理没啥关系，所以我们先来复习一下中国剩余定理。 同余方程组 $$\begin{cases}x \equiv a_1 \pmod {m_1} \equiv a_2 \pmod {m_2} \quad \vdots \equiv a_n \pmod {m_n} \end{cases}$$ 当 $m…