本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-22 09:21:31

二轮省集发现自己啥都不会，决定学点新东西，于是就学了。事实上拖到三轮之后很久才写完。

树状数组上倍增

不难但我刚学。树状数组上 $b_i$ 代表原数组 $[i-w(i)+1,i]$ 的和，其中 $w(i)$ 为 $i$ 的 lowbit 值。因此枚举 $k$ 从 $\lfloor \log n\rfloor$ 到 $0$，初始指针 $p$ 为 $0$。每次查询当前 $[p+1,p+2^k]$ 之和 $b_{p+2^k}$ 是否达到目前 $x$。若未达到则将 $x$ 减去区间和，并更新 $p\leftarrow p+2^k$，否则不更新。最终 $p$ 即为前缀和小于 $x$ 的最大位置。使用 CF1070C 进行了测试，所用时间大概是线段树二分或二分 + 树状数组的一半。

树状数组维护区间和

考虑维护差分数组 $d_i=a_i-a_{i-1}$，区间 $[l,r]$ 加上 $x$ 即为 $d_l=d_l+x,d_{r+1}=d_{r+1}-x$，容易修改。查询时差分成前缀和，有前缀和 $s_k=\sum_{i=1}^k a_i=\sum_{i=1}^k\sum_{j=1}^i d_j$，交换求和号得到 $s_k=\sum_{j=1}^k(n-j+1)d_j=(n+1)\sum_{j=1}^k d_j-\sum_{j=1}^kjd_j$，用树状数组分别维护 $d_j,jd_j$ 前缀和即可，代码。若要查询 $ia_i$ 的区间和同样可推得 $s_k=\sum_{j=1}^k\sum_{i=j}^k id_j$，等差数列求和得 $s_k=\frac 12\sum_{j=1}^ k[(k^2+k)d_j+jd_j-j^2d_j]$，需要额外维护 $j^2d_j$ 的前缀和。

历史和

需要支持区间加，查询区间历史和。历史和定义为 $h_i$ 的区间和，初始 $h_i=a_i$，每次操作之后均更新所有 $h_i\leftarrow h_i+a_i$。以下做法时间复杂度均为 $O(n\log n)$，但常数上有较大差异。

Sol.1

考虑使用矩阵维护，设 $l,s,h$ 分别为区间长度，区间和和区间历史和，则当区间加 $x$ 时， $$ \begin{bmatrix} l &s&h\end{bmatrix}\begin{bmatrix} 1&x&0\\ 0&1&0\\ 0&0&1\end{bmatrix}=\begin{bmatrix} l &s+lx&h\end{bmatrix} $$ 更新一次历史和时， $$ \begin{bmatrix} l &s&h\end{bmatrix}\begin{bmatrix} 1&0&0\\ 0&1&1\\ 0&0&1\end{bmatrix}=\begin{bmatrix} l &s&h+s\end{bmatrix} $$ 因此直接使用线段树维护矩阵，矩阵乘法维护标记即可，常数较大，代码。

Sol.2

观察上个做法中的矩阵，注意到均为上三角，且对角线均为 $1$，有 $$ \begin{bmatrix} 1 &a&b\\ 0&1&c\\ 0&0&1\end{bmatrix}\begin{bmatrix} 1&x&y\\ 0&1&z\\ 0&0&1\end{bmatrix}=\begin{bmatrix} 1&a+x&b+y+az\ &1&c+z\&0&1\end{bmatrix} $$ 因此只记录 $x,y,z$ 三个数即可表示矩阵，合并方式即上式，常数会小很多，代码。

Sol.3

考虑拆每个修改的贡献。具体地，若在第 $t$ 次操作时给某位置加了 $x$，则第 $T$ 次操作询问时，该修改的贡献为 $(T-t)x=xT-xt$，是关于 $T$ 的一次函数，因此分别维护两个系数的区间加、区间和即可。线段树，树状数组，树状数组做法在提交时为本题最优解。

Sol.4（25.10.28 补充）

lxl 讲了这个，所以记一下。考虑标记序列，其由若干加标记和历史和标记构成。相邻相同标记可以直接合并，于是两种标记交替出现。尝试交换标记，发现可以将历史和标记全扔到最后，这会导致历史和多加了一些加标记的值，再开一个标记变量记录一下就行。

具体地，标记为 $(t,c,h)$，表示先加 $t$，再累加 $c$ 次历史和，再给历史和加上 $h$。标记的合并为 $(t_1,c_1,h_1)+(t_2,c_2,h_2)=(t_1+t_2,c_1+c_2,h_1+h_2-c_1t_2)$。信息为 $(s,c,h)$，分别表示当前和，区间长度和历史和，信息的合并是容易的，信息与标记合并为 $(s,c,h)+(t',c',h')=(s+t',c,h+c(c's'+h')+c's)$，直接上线段树即可，常数大概跟矩阵拆成三个数差不多，提交记录。

历史最值：P4314 CPU 监控

需要支持区间加、区间赋值以及求区间最大值、区间历史最大值。令区间加标记为 $ta$，考虑额外维护一个标记 $tb$，表示未下放标记的历史最大值。给 $x$ 加标记时先尝试用 $x+tb$ 更新历史最值，再更新 $x\leftarrow x+ta$。标记的合并也一样，如将 $(ta',tb')$ 合并到 $(ta,tb)$ 上时，先尝试用 $ta+tb'$ 更新 $tb$，再更新 $ta\leftarrow ta+ta'$。

加上区间赋值时，若无历史最值要求，则赋值标记 $ca$ 和加标记 $ta$ 不会同时存在，即赋值时会清空加标记，区间加时若存在赋值标记则更新赋值标记，而不是添加加标记。此时为了求历史最值，也需额外维护一个标记 $cb$，表示未下放覆盖标记的历史最大值。此时赋值只清空 $ta$ 而保留 $tb$，因为历史最值还需要更新；区间加时若存在 $(ca,cb)$ 同样更新 $(ca,cb)$ 即可，合并方式同上。注意为了正确地用 $tb$ 更新历史最值，在 pushdown 时要先下放 $(ta,tb)$，再下放 $(ca,cb)$。时间复杂度 $O(n\log n)$。提交记录。

区间最值操作、区间历史最值：P6242 线段树 3

需要支持区间加，区间对一个数取 min 以及求区间和、区间最大值、区间历史最大值。若无 checkmin 操作，可直接用上题做法维护。考虑到对 $x$ 取 min 是把大于 $x$ 的数减到了 $x$，然而不同数所减值也不同，难以用标记统一维护。因此再维护区间次大值 $cmx$，只在 $cmx\le x< mx$ 时用标记记录 $mx$ 的变化，标记形式为记录历史最值的两个值 $(ta,ma)$，否则直接暴力递归到子节点中。

此时再用 $(tc,mc)$ 标记记录非最大值的情况。区间加时两者都合并上 $(x,x)$，checkmin 到合法节点时只给最大值标记合并上 $(x-mx,x-mx)$ 即可。标记下传时讨论子节点最大值是否是整个区间最大值，若是则分别用 $(ta,ma),(tc,mc)$ 更新两组标记，否则均用 $(tc,mc)$ 更新。具体地，先取 $X=\max(mx_l,mx_r)$，再用 $X$ 来判断 $mx_l,mx_r$ 是否为最大值。这里不能直接用父亲节点最大值 $mx_u$，因为此时父亲节点可能已被修改，而要判断的是最大值是否为修改前的区间最大值。

该算法正确性没有问题，时间复杂度单点修改时为 $O((n+m)\log n)$，可以使用不同数的个数证明，即若暴力递归，则有 $x<cmx$，本次操作后该节点不同数个数会减少，由于线段树每层都只有 $O(n)$ 个不同的数，共 $O(n\log n)$ 个，单点修改时只会增加 $O(m\log n)$ 个，总递归次数得到保证。至于本题的区间加我不会证，但跑出来看着挺对的，至少不超过 $O(n\log n+m\log ^2 n)$。论文里还提到可能比这更低，也有讨论说不一定是真的，可以自己去看。

P10639 最佳女选手

需要支持区间加，区间对一个数取 min/max 以及求区间和、区间最大最小值。类似上题，在每个节点上维护区间最大、次大、最小、次小值，再分别维护所有值、最大值、最小值的加标记。最值操作时同样只在单值修改时打标记修改，否则暴力向下递归。需要注意节点内只有单个值 / 两个值时要注意最值的更新，有点细节。时间复杂度同样不高于 $O(n\log^2 n)$，同样不会证，提交记录。

树套树：P3380

或许不怎么考，但本着练码力的目的还是写了。

注意到所有操作均可用平衡树或权值数据结构完成，这时加入区间限制，考虑使用树套树，即在外层数据结构每个节点上开一个内层数据结构，查询时在外层数据结构上找到所查询区间，用这些内层数据结构进行查询即可。

对于本题，外层可使用线段树。内层若使用平衡树，则需对其进行合并，总复杂度会达到 $O(m\log ^3n)$，且我不想写平衡树。因此内层使用动态开点权值线段树，这样也能保证空间复杂度为 $O((n+m)\log^2n)$。找出 $O(\log n)$ 棵树后，对这些树同时求区间和或二分即可。注意若外层为树状数组则需要差分，需要记录贡献系数。

另外对于前驱后继查询，除了线段树上二分之外，外层线段树时可直接额外开 $n$ 个 set，查询时多次询问取最值。然而外层树状数组时需差分，不能用 set 简便操作。然而 $x$ 的前驱即 $kth(rk(x)-1)$，后继即 $kth(rk(x+1))$，因此只需要实现区间和和二分出第 $k$ 小即可，常数也没大多少。时间复杂度 $O((n+m)\log ^2n)$，提交记录。

动态树：P3690

要求维护带点权的森林，支持连边、删边、单点修改，查询路径异或和。LCT 是对树进行实链剖分得到的，钦定每个点连向其儿子的边中某一条为实边。对每条实链以深度为键值建出 Splay 后，再以原树中链头父亲为 LCT 中 Splay 根节点的父亲。注意这样跨实链的边有“认父不认子”特点，该父节点的子节点是 Splay 结构，而不记录跨实链的儿子，可以以此判断某点是否为 Splay 的根。下面是基本操作：

• access(x)：在 LCT 中将 $x$ 到根的路径变成一条完整实链。

由 $x$ 跳到根，每次先将 $x$ splay 至当前 Splay 的根，然后将其右儿子赋为上个 $x$，再令 $x\leftarrow f_x$。这样使得路径上所有边均变为实边，且最初 $x$ 的右儿子为 $0$，即已经是实链链底，这样就实现了 access 操作，注意过程中要进行 pushup 更新。

• makeroot(x)：将 $x$ 变为其所在树的根节点。

考虑先 access(x)，这样 $x$ 变成了实链链底。然后将其 splay 至根，其右儿子一定为空。这时将整棵 Splay 翻转，就让其变成了整棵树的根。为了实现翻转操作需要使用懒标记。

• findroot(x)：查询 $x$ 所在树的根节点。

先 access(x) 并 splay(x) 到根，然后从 $x$ 一直跳左儿子得到中序遍历最前的点即为根。向下跳前时需要下传懒标记，且找到根节点后要将其 splay，以保证依赖势能的复杂度。另外若不 splay 在模板题中会出现神秘错误，我还没想清楚是为什么。

• split(x,y)：将 $x,y$ 之间的路径变为一条实链（一棵 Splay）。

容易想到 makeroot(x),access(y) 即可实现，为了保证复杂度需要 splay(y)，同时这样也使得 $y$ 变为根，该路径即为 $y$ 的整个子树。

• link(x,y)：若两点不连通，增加一条 $x,y$ 之间的边。

先 makeroot(x)，这时若 findroot(y) 不为 $x$ 则两点不连通，由于 $x$ 已为根，直接将其父亲赋为 $y$ 即可，不会破坏实链剖分的结构。

• cut(x,y)：若两点之间有边则将其断开。

先 makeroot(x)，这时需要 $y$ 所在树根为 $x$，$x$ 为 $y$ 父亲且 $y$ 没有左儿子，三个条件均满足时 $x,y$ 相连，$y$ 为 $x$ 右儿子。将 $x$ 右儿子和 $y$ 父亲均清空即可断边，注意此时要进行 pushup 更新。

其他细节：rotate 不能跨虚边操作，只在跨实边时更新儿子；splay 前要把该 Splay 内根到该节点的所有点依次 pushdown，保证标记正确。模板题使用上述操作即可实现，提交记录。时间复杂度均摊 $O(q\log n)$，我不会证。

P1501 Tree II

维护一棵树，支持删边再加边，路径加，路径乘以及求路径和。删边和加边操作与模板相同，需要维护的是修改操作。这里类似线段树 2，设计加标记和乘标记，路径乘时同时给两个标记乘即可。需要注意的是 LCT 上要同时更新子树值和单点值，才能保证答案正确。是比较板的懒标记 LCT，时间复杂度 $O(q\log n)$，提交记录。

全局平衡二叉树

可以认为是静态的 LCT 结构，要求树高为 $O(\log n)$ 级别，以方便进行点到根的路径操作。具体做法为先重链剖分，每条重链以深度为键值建二叉搜索树，重链间以虚边连接，同样“认父不认子“。建二叉搜索树时以虚子树总点数为点权，以带权重心为根并递归到两边建子树。这样重链内部每次向上跳会让子树大小翻倍，而每个点到根的路径只有 $O(\log n)$ 条轻边，因此总树高为 $O(\log n)$。

这时点 $x$ 到根的路径可在 GBT 上跳到根得到，开一个布尔变量 $v$ 记录目前是否在所求路径上。跳父亲时若 $x$ 为父亲左子树，则父亲深度比 $x$ 大，不在路径上；为右子树或跨过轻边时父亲深度均比 $x$ 小，还在路径上，因此跳之前设 $v=[x\ne lc_{f_x}]$ 即可。访问时 $v=1$ 的所有点 $u$ 及其左子树的并为原树中 $x$ 到根的路径，可以使用子树标记维护。

P4211 LCA

先将询问差分成前缀，转化为给出 $x,k$，求 $\sum_{i=1}^k w(i,x)$，其中 $w(i,x)$ 表示 $i$ 和 $x$ 的 LCA 深度。注意到两点 LCA 深度即为两点到根路径交的长度，因此对所有 $i$ 到根的路径加 $1$ 后，查询 $x$ 到根的路径和即为所求。

因此需要支持某点到根路径加，求某点到根路径和。容易使用树剖做到 $O(q\log ^2n)$，这是使用线段树的代码 A 和使用树状数组的代码 B。然而某点到根的路径显然可以使用 GBT，用懒标记维护子树加即可，时间复杂度 $O((n+q)\log n)$，代码 C。如果使用标记永久化技巧，可以避免从根 pushdown 一遍的常数，代码 D。最终运行时间为 $D<B<C<A$，中间两种差距较小，所以树状数组真王朝了。

P4719,P4751 动态 DP

不带修是简单树形 DP，设 $f_{i,0/1}$ 表示 $i$ 子树内是否选 $i$ 点时的最大点权和，转移为 $f_{u,0}=\sum\max(f_{v,0},f_{v,1}),f_{u,1}=\sum f_{v,0}+a_u$，其中 $v$ 为 $u$ 子节点。考虑若修改点权，则其到根路径上所有点的 DP 值均需要更新，然而暴力跳到根复杂度难以接受，需要快速修改。

考虑用矩阵刻画 DP 转移，从而让 DP 过程变成矩阵乘法，方便单点修改。由于要求最优化，使用 max+ 矩阵，即 $c_{i,j}=\max(a_{i,k}+b_{k,j})$ 的矩阵维护。为了快速更新，先进行重链剖分，再设 $g_{i,0/1}$ 表示不考虑 $i$ 的重儿子时的 DP 值，则有 $f_{u,0}=g_{u,0}+\max(f_{son_u,0},f_{son_u,1}),f_{u,1}=g_{u,1}+f_{son_u,0}$。此时便有： $$ \begin{bmatrix} f_{son_u,0} & f_{son_u,1}\end{bmatrix}\begin{bmatrix} g_{u,0}&g_{u,1}\\g_{u,0}& -\infin\end{bmatrix}=\begin{bmatrix} f_{u,0}&f_{u,1}\end{bmatrix} $$ 因此在每个点上维护上式中的矩阵，某点的 DP 值即为其所在重链链底到该点的路径矩阵乘积。单点修改时 $g_{u,1}$ 会改变，从而其所在重链链头 DP 值改变，又使得跨过轻边后的父亲 $g$ 值改变。因此向上跳 $O(\log n)$ 条重链，每次修改其对下一条重链的影响即可。使用线段树维护矩阵乘积是 $O(q\log ^2n)$ 的，不卡常只能通过 $n,q\le 10^5$ 的 P4719，提交记录。可使用 GBT 维护，只在跳轻边时更新，复杂度 $O(q\log n)$，提交记录，可以通过加强版。

并查集

别问为什么会在这里，因为我之前不咋懂而且下面要用。

之前我甚至没写过合并优化。

按秩合并 / 启发式合并

合并时将高度小的并查集合并到高度大的，或是将大小小的合并到大小大的，两种做法的单次复杂度均为 $O(\log n)$。如果再加上路径压缩，复杂度会降到总共 $O(q\lpha(n))$，使用大小启发式合并的提交记录。虽然单独使用路径压缩同样也是 $O(q\log n)$，然而其会破坏树的结构，在某些情况下只能优化合并来保证复杂度。

可撤销并查集

特殊情况来了，要求支持撤销最后一次有效合并。由于路径压缩会改变树的形态，难以撤销，只能优化合并。开一个栈记录所有被修改 $f$ 值的 $x$，要撤销时拿出栈顶 $x$ 直接改回 $f_x=x$ 即可，还要将变化的 $s$ 值修改回去。这里按大小启发式合并更容易复原，因此采用这种写法。时间复杂度 $O(q\log n)$，提交记录。

扩展域并查集：P1525 关押罪犯

其实比较简单，在本题中即给每个元素新开一个点 $n+i$，令 $i,n+i$ 分别表示 $i$ 点放到两个不同监狱中。把关系按影响力从大到小排序后依次处理，每次先分别合并 $u,n+v$ 和 $v,n+u$，若此次合并导致 $u,n+u$ 或 $v,n+v$ 在同一集合内，则已经出现冲突，答案为该关系的影响力。并查集操作与模板相同，复杂度可以做到 $O(q\lpha(n))$，提交记录。

线段树分治

若操作在某个时间段内有效，可以离线后在时间轴上建线段树，并把操作拆到 $O(\log V)$ 个线段树节点上。之后遍历整棵线段树，进入某节点时执行所有该节点上的操作，遍历完子树后回溯时将操作撤销，在每个叶子节点上统计对应时刻的答案即可。

P5787 二分图

每条边在一段时间内存在，询问每个时刻整个图是否为二分图。二分图判断可以使用扩展域并查集维护，每条边都变成了两次合并操作。使用线段树分治，将其放到 $O(\log n)$ 个节点上。遍历时若在某点出现冲突，则其内部所有时刻均非法，可以直接回溯；若到叶子节点仍未冲突，则该时刻合法。回溯时用栈维护可撤销并查集即可实现，总时间复杂度为 $O(m\log k\log n)$，为操作数乘上单次操作复杂度，提交记录。

CF1814F Communication Towers

点的存在不好处理，不妨转化为边存在，即边 $(u,v)$ 在 $[\max(l_u,l_v),\min(r_u,r_v)]$ 内的时刻存在，可以像上题一样用可撤销并查集维护连通性。统计答案需要在每个时刻给 $1$ 所在的连通块打标记，考虑设 $w_i$ 表示 $i$ 点与 $1$ 连通的时刻数量。每个时刻给 $1$ 所在连通块根节点标记加 $1$，$x$ 合并到 $y$ 时先给 $w_x$ 减掉目前 $w_y$，撤销该操作时给 $w_x$ 加上此时的 $w_y$，从而差分得到跟 $y$ 连通时的实际贡献。最后所有边均消失，每个点独立，输出所有 $w_x>0$ 的 $x$ 即为答案。时间复杂度 $O(m\log V\log n)$，提交记录。