【学习记录】数据结构

KSCD_ · 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 时，

更新一次历史和时，

因此直接使用线段树维护矩阵，矩阵乘法维护标记即可，常数较大，代码。

Sol.2

观察上个做法中的矩阵，注意到均为上三角，且对角线均为 1，有

因此只记录 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}。此时便有：

因此在每个点上维护上式中的矩阵，某点的 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\alpha(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\alpha(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)，提交记录。

K-D Tree：P14312

维护 k 维空间，支持加入点，超立方体内点加，查询超立方体内点值和。k\le3,q\le 1.5\times 10^5,1\le x\le 10^{18}。

考虑每次选择某个维度，按该维度坐标排序。之后以某点为树根将所有点分成两半，递归建左右子树，直到只剩一个点时返回该点。这里选择维度时每次选上层的下一个维度，从而保证每 k 层每个维度被分一次；树根每次取中位数，保证树高为 \mathcal O(\log n)，这样在上面找某个超立方体的复杂度可分析为 \mathcal O(n^{1-\frac 1k})，不会证。具体建树时可以使用 nth_element 找中位数并归位，总复杂度为 \mathcal O(n\log n)。

不过要加入点时 K-D Tree 的结构会被破坏，需要根号重构或二进制分组解决。这里采用常数小的二进制分组，具体地，维护若干棵 K-D Tree，每棵内点数为 2^k。加入新点时从低到高合并若干棵树，将这些点建成一个 2^t 大小的新树，查询也在所有树上均查询即可。插入复杂度 \mathcal O(n\log ^2n)，修改查询复杂度 \mathcal O(qn^{1-\frac 1k})，提交记录。