位图

位图

位图是 $n$ 个 0 或 1 的数据组成的列表

可以在 $O(1)$ 时间内实现 test, set, clear 操作

应用

• 去重

快速初始化

• 拆分数组+校验环
• 将 Bitmap 拆分成 From 和 To 两个数组，当且仅当 To[From[k]] == k && From[k] < top 才表示第 k 位为 1
• T 数组类似一个栈，维护一个栈顶指针 top
• 重置：top = 0;
• 插入：T[top] = k; F[k] = top++;
• 删除：只将 T 数组的末尾移动到空缺处并更新对应的 F 数组。F[T[top]] = F[k]; T[F[k]] = T[top];
• 实现 $O(1)$ 的操作，但是空间复杂度有所增加，原本只存 1 bit，现在需要存一个 Rank