跳转至

数组

所有代码实现见 Java数据结构与算法

堆

堆可以用数组进行实现，堆是个完全二叉树。

并查集

假设元素间有关联，且存在传递关系，如何快速判断两个元素是否有关联。

用途

1、维护无向图的连通性。支持判断两个点是否在同一连通块内； 2、判断增加一条边是否会产生环：用在求解最小生成树的Kruskal算法里；

定义：管理一系列不相交的集合，只支持两种操作：

  • 合并（Union）：把两个不相交的集合合并为一个集合。
  • 查询（Find）：查询两个元素是否在同一个集合中。

初始版本（合并复杂度/查询复杂度：O(h)，h表示树的高度，最差为链表）

算法过程：每个元素只知道自己的父节点；

  • 初始每个元素父节点即自身或者 -1，ids[i] = i；

  • 查找元素所属的集合

int find(i) {
    while (ids[i] != i) {
        i = ids[i];
    }
    return i;
}

  • 合并两个元素时，将其中一个节点的集合指向另一个节点，ids[find(i)]=j；

  • 判断两个是否处于同一个集合，find(i)==find(j)；

路径压缩

  • 解决查找时次数过多的问题，防止树变成链表，查找复杂度变为O(n)；
  • 查找时将x到根节点路径上的所有点的parent设为根节点，该优化方法称为压缩路径

按秩合并

  • 维护每个子树的节点个数，合并时将小的子树合并到大的子树上
  • 如果是维护子树的高度，则路径压缩会造成rank不准确，因此按照 size 进行合并；

unionset_ops

树状数组

树状数组（Binary Index Tree, BIT），最简单的树状数组支持两种操作，时间复杂度均为 Olg(n)：

  • 单点修改：更改数组中一个元素的值
  • 区间查询：查询一个区间内所有元素的和

对于普通数组而言，单点修改的时间复杂度是O(1)，但区间求和的复杂度是O(n)。

原理

树状数组的定义：

  • 二进制数最右边的一个1，连带着它之后的0为\(lowbit(x)\)，用\(C(i)\)维护区间\((A_i-lowbit(A_i), Ai]\)，这样查询前n项和时需要合并的区间数是少于\(log_2(n)\)：

tree_array

更新就是一个“爬树”的过程。一路往上更新，直到MAXN（树状数组的容量）。

tree_array_update

\(lowbit(x)=(x)\&(-x)\)