数据结构问题 ​

处理区间问题的常见办法 ​

差分 ​

前缀和，主席树。

线段树 ​

• 首先考虑区间维护什么信息，如何 push_up。
• 若有区间修改，考虑如何打 tag，如何快速修改区间信息。

分块 ​

• 序列分块，时间轴分块。
• 优化暴力。

莫队 ​

考虑左右端点的扩展和收缩如何维护答案。

定右端点扫描线 ​

没有修改时的首选算法。

“跳端点”的询问 ​

倍增，跳端点分治。

可撤销相关 ​

任意顺序 ​

• 01 背包方案数
• 高维前缀和

一般的，需要满足以下条件：

• 计数 DP
• 运算可撤销（例如加法、乘法）

固定顺序 ​

按秩合并并查集。

常见做法 ​

• 莫队：一般是任意顺序的，区间查询，不支持修改。
• 线段树分治：任意顺序或固定顺序，单点查询，区间修改。

染色问题 ​

修改 ​

单点修改，区间推平，区间加颜色。

查询 ​

区间颜色数。

常见算法 ​

• 莫队：单点修，区间颜色数。
• 线段树维护颜色状压：区间加颜色，区间颜色数。
• 线段树维护 pre 数组：单点修，区间颜色数。
• ODT：区间推平，构成颜色段均摊。
• 转化成二维数点问题：区间推平，区间颜色数。

区间 mex 问题 ​

区间扩展和收缩 ​

结合桶，维护没有出现过的数，每次最小的就是 mex。

区间在线求 mex ​

• 维护 $n\times n$ 的矩阵，$t[i][j]$ 表示在 $a[1\sim i]$ 中，数 $j$ 最后一次出现的位置。
• 一个数 $x$ 在 $[l,r]$ 中出现等价于 $a[r][x]\geq l$。
• 想办法维护这个矩阵即可。
• 具体做法：
  • 在线：可持久化线段树上二分。
  • 离线：扫描线 + 线段树上二分。

根号分治 ​

发现条件 ​

反的单调性。

常见形式 ​

分式形式 ​

• 条件：分子一定。
• 分式值和分母做平衡。

和一定形式 ​

• 具体的，有：度数和点数，连通块数和块的大小等。
• 结论一：数的大小和数量做平衡。
• 结论二：数的种类是根号级别的。这其实基于结论一：
  • 小数就是有根号种（可能有重复的）。
  • 大数就是根号个（有重复也没关系）。

线段树合并 ​

处理 ​

与普通的动态开点线段树相同，支持懒标记下传，其特殊的是：当 ls 和 rs 有一个不为空时就下传，否则不下传。

复杂度 ​

修改时遍历的节点数级别。

proof ​

• 首先，懒标记下传产生的新节点数和修改时遍历节点数、合并时遍历节点数同阶，可以不管。
• 考虑在所有线段树中同一个节点的所有修改操作次数 $x$。
• 假如没有额外的分裂，那么该节点在 merge 函数中被遍历不 return 的次数就是 $x - 1$。
• 那么，整个树的 merge 调用次数就是和修改操作遍历节点个数同级。

启发式 ​

核心 ​

在和一定的情况下，只遍历较小的那个集合。

注意 ​

• 关注根据什么来做启发式，不是所有时候都是节点个数。例如，在既要遍历子树，又要遍历子树中的询问的时候，就认为集合大小是节点数 + 询问数。
• 关注启发式做法的常数，只要想卡，是容易卡到对数的。

启发式合并 ​

• 实现：将小集合中的元素逐个插入到大集合中。
• 适用范围：
  • 插入复杂度（实现难度）低于合并。
  • 集合总量可以接受。
• 常见运用：set 合并。

启发式分裂 ​

• 实现：通过同步扫描，不断裂出已经扫完的部分。
• 适用范围：自己看着办。

点分治的实现问题 ​

点分治类型 ​

点分治有两种，一种是计数，一种是最优化。

计数类方便实现方法 ​

• ans += solve(rt); // 直接统计当前分治树的点对贡献
• ans -= solve(son); // 容斥掉 rt 的各个子树的不合法部分

而对于 solve(x) 函数，通常可以把所有点都放进一个序列里，然后直接用某些离线做法。这样可以避免用一些在线数据结构，代码更好写，复杂度也更优。注意，这种做法不用考虑从 rt 出发的某些特殊情况。

通用实现方法 ​

• 涉及最值的，可以优先考虑法二。

法一 ​

• 利用某些在线数据结构，先把所有点都加进去；当要统计某棵子树的贡献时，就再把其贡献删掉，统计完再加回来。
• 但是，在某些最优化中，我们可以不用又删又加的，可以直接维护最大次大值，本质和换根 DP 相似。
• 注意，这种做法必须考虑从 rt 出发的某些特殊情况。

法二 ​

• 考虑正着扫的同时加入一棵棵子树的贡献，然后再清空，再倒着做一遍。
• 通常用于处理删除操作不好实现的情况。
• 如果路径无序，则不需要再倒着做一遍。

点分治卡常的常见办法 ​

• 多次调用，先建出点分树。
• 灵活选用上述的各种写法（一定要在 coding 之前确定当前做法最简）。

树上对链或连通块的查询问题处理 ​

类型 ​

• 求最优的连通块
• 求最优的链
• 查询某条链对应的信息
• 查询某个连通块对应的信息（一般带修）

带修 ​

• 树链剖分：处理查询问题。
• cdq：处理查询和最优化问题。

不修 ​

• 比较通用的做法：
  • 树链剖分：处理查询问题。
  • 点分治：可以处理查询和最优化问题。
  • 换根：处理对于每个起点的链查询，可以结合 DP 或 dfs 序。
• 如果使用了点分治，可能可以有如下进阶办法：
  • 直接在 lca 处处理对应的链：
    • 核心难点：处理链的合并。
    • 常用相关算法：
      • dsu on tree
      • 线段树合并

可持久化数据结构 ​

处理办法 ​

将改变了的节点新建出来，作为新的版本。这样的时空做法复杂度就是和修改的节点数相同的。

结论 ​

基于均摊/势能分析的做法可持久化的复杂度是：单次操作降到其最劣修改复杂度。

proof ​

只要每次做最劣修改然后再回退即可。

常见例子 ​

• 路径压缩的并查集
• splay