knowledge-datastructure

Table of Contents

LCT

树链剖分

例题

CF 504E

点分治

每次处理一棵子树, 首先找到这棵子树的重心, DFS这棵子树并统计相关信息, 然后删去重心, 分别递归至删去重心后原子树的每一部分, 除非删去后就没有其他节点了.
由重心的性质可得: 裸的点分治复杂度为 O(nlogn).

合法路径(点对)统计

在每一层分治结构中, 由于所有的边都被拆成了经过根的边, 所以可以用数据结构维护, 使得对于一个节点可以查询有分治结构中有多少个节点与其组成的路径合法.
但是这样会算入不合法的路径. 即两个节点的 LCA 不是分治结构的根时. 此时两个节点在同一棵子树中. 用同样的方法统计出对之前查询的贡献并减去即可.

最优路径(点对)统计

和上面类似, 但是处理起来会比上面麻烦. 因为一般不满足区间可减, 为了不统计同一子树的信息, 我们可能需要维护一下前缀信息和后缀信息, 然后两份信息合并得到除这棵子树的信息.
有时可能需要使用可持久化数据结构节省空间.

不过如果满足不合法的路径一定不是最优路径, 倒是无所谓.

例题

BZOJ 3772

边分治

例题

SPOJ 2666 tsinsen 1486

树分块

树上莫队

块状树

考虑先将原树转为二叉树, 保证复杂度.

例题

DFS序

BFS序

欧拉序

LCA

树上倍增

子树信息合并

例题

UOJ 33

相关问题

  1. SAFFIX-ARRAY 查询一段字符串是哪些后缀的开头的查询结果满足树形结构.
  2. http://www.cnblogs.com/zzqsblog/p/6146916.html

生成树

矩阵树定理

例题

LA 7138

环套树

有向环套树

一般而言, 假设一个图中每个点的出度均为1, 那么这一定是一个有向环套树森林.

相关例题

CF 739D

平衡树

splay

旋转Treap

分裂合并Treap

替罪羊树

线段树

动态开点线段树

线段树合并

划分树

主席树

二进制分组

K-D树

一般采用类似于平衡树的结构. K-D树中的某一节点的子树表示的是某一高维 立方体 内的所有的点. 其左儿子和右儿子将这个高维空间继续拆分, 但是不包括当前的根节点. 为了高效实现某些操作, 每个节点需要维护以该节点为根的子树表示的高维空间的边界. 由于是立方体, 只需记录每一个维度坐标的最大值和最小值即可.

轮换分割

这是建树的一种方式, 因此左儿子和右儿子的点数应尽可能相等. 为了拆分某一高维空间, 我们不妨从某一维度拆分: 在这个维度上, 坐标较小的往左儿子走, 坐标较大的往右儿子走. 所以我们找出所有点在这一维度上坐标的中位数, 作为这棵子树的根, 坐标比它小的递归至左儿子, 坐标比它大的递归至右儿子.

如果使用 std::nth_element 找中位数, 复杂度为 \(O(n \log n)\); 如果使用 std::sort, 复杂度 \(O(n \log ^2 n)\).

矩形查询

以查询点数为例. 如果查询的矩形与当前子树表示的矩形无交, 则返回0; 如果当前子树表示的矩形被完整的覆盖, 则返回该子树内的点数. 否则, 递归左右子树, 返回左右子树的查询结果之和. 拓展到高维空间也是一样的. 假设是 \(k\) 维空间, 其单次查询的复杂度为 \(O(n^{1 - \frac{1}{k}})\), 其中 \(n\) 为 K-D树的点数.

最近邻 (玄学复杂度)

查询K-D树中离某一点最近的点. 对每个节点定义一个估价函数, 表示在最好的情况下, 这个子树中离查询的点最近距离为多少. 从根节点开始查询. 如果比当前答案优, 则用该子树的根节点更新答案, 并递归左右儿子. 递归左右儿子时要注意顺序. 先递归估价函数值较小的. 否则结束对该节点的查询.

k近邻 (玄学复杂度)

在最近邻的基础上套一个大根堆来记录答案.

支持插入操作并保持平衡

本质是平衡树, 所以用 替罪羊树 的思想即可.

树状数组

std::map 实现动态开点 O(n log2 n)

二叉堆

斜堆

可并堆

可持久化数据结构

可持久化栈

可持久化线段树

可持久化Treap

可持久化堆

HOME