浅谈分层位图索引:一种 O(\log_w V) 求前驱和后继的算法
xingtiankai2023
·
·
算法·理论
分层位图索引:一种 O(\log_w V) 求前驱和后继的算法
摘要:本文介绍一种叫「分层位图索引」的数据结构。它维护一个动态集合 S\subseteq\{0,1,\dots,V-1\},支持 O(\log_w V) 插入、O(\log_w V) 删除、O(\log_w V) 查询前驱 / 后继,内存只有 V/8 字节。
前置知识:位运算、__builtin_ctzll(O(1) 查询 ull 尾部 0 的数量,以下简称 ctz),__builtin_clzll(O(1) 查询 ull 头部 0 的数量,以下简称 clz)。
一:它到底要解决什么问题:查询前驱和后继
有一类问题长这样:
维护一个动态集合 S\subseteq\{0,1,\dots,V-1\},支持插入、删除,以及查询
\operatorname{succ}(x)=\min\{y\in S:y\ge x\},\qquad \operatorname{pred}(x)=\max\{y\in S:y\le x\}
常规的解决办法有如下几种:
- 线段树:O(\log V) 修改,O(\log V) 查询。
- 平衡树:O(\log V) 修改,O(\log V) 查询。
- bitset:O(1) 修改,O(\frac{V}{w}) 查询。
而分层位图索引则能做到 O(\log_w V) 修改和 O(\log_w V) 查询。
二:结构
这里我们以 V = 2^{18} = 262144 \approx 2.5\times 10^5 举例,这也是实践中最常用的,当然如果对于更大的值域我们只需要建四层位图即可。
- 第一层 v1:4096 个
ull,每个 bit 存储一个值是否存在。
- 第二层 v2:64 个
ull,每个 bit 存储第一层的值是否非 0。
- 第三层 v3:1 个
ull,每个 bit 存储第二层的值是否非 0。
三:实现
插入一个元素
只需要从下往上逐层更新。
:::info[代码]
void insert(int x) {
if (++cnt[x] != 1) return;
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1];
v1[b1] = w | (1ull << c1);
if (w) return;
int b2 = b1 >> 6,c2 = b1 & 63;
w = v2[b2];
v2[b2] = w | (1ull << c2);
if (w) return;
v3 |= 1ull << b2;
}
:::
删除一个元素
同上。
:::info[代码]
void erase(int x) {
if (--cnt[x]) return;
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1] & ~(1ull << c1);
v1[b1] = w;
if (w) return;
int b2 = b1 >> 6,c2 = b1 & 63;
w = v2[b2] & ~(1ull << c2);
v2[b2] = w;
if (w) return;
v3 &= ~(1ull << b2);
}
:::
查询最小值
从上往下每层用 ctz 查询第一个 1 出现的位置。
:::info[代码]
int find_min() { // 求最小值
if (v3 == 0) return -1;
int r3 = ctz(v3);
int r2 = ctz(v2[r3]);
int r1 = ctz(v1[(r3 << 6) + r2]);
return (r3 << 12) + (r2 << 6) + r1;
}
:::
查询最大值
从上往下每层用 clz 查询最后一个 1 出现的位置。
:::info[代码]
int find_max() { // 求最大值
if (v3 == 0) return -1;
int r3 = 63 - clz(v3);
int r2 = 63 - clz(v2[r3]);
int r1 = 63 - clz(v1[(r3 << 6) + r2]);
return (r3 << 12) + (r2 << 6) + r1;
}
:::
查询后继
先从下往上逐块查询下一个 1 所在的块,在该块往下查询。
:::info[代码]
int find_next(int x) { // 查询>=x中第一个为1的位置
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1] & (~0ull << c1);
if (w) return (b1 << 6) + ctz(w);
int b2 = b1 >> 6,c2 = b1 & 63;
if (c2 < 63) { // 查询同一组里b1之后的1
w = v2[b2] & (~0ull << (c2 + 1));
if (w) {
int nb = (b2 << 6) + ctz(w);
return (nb << 6) + ctz(v1[nb]);
}
}
if (b2 < 63) { // 查询更高组的1
w = v3 & (~0ull << (b2 + 1));
if (w) {
int nb2 = ctz(w);
int nb = (nb2 << 6) + ctz(v2[nb2]);
return (nb << 6) + ctz(v1[nb]);
}
}
return -1;
}
:::
查询前驱
同上。
:::info[代码]
int find_prev(int x) { // 查询<=x中第一个为1的位置
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1] & (~0ull >> (63 - c1));
if (w) return (b1 << 6) + 63 - clz(w);
int b2 = b1 >> 6,c2 = b1 & 63;
if (c2) {
w = v2[b2] & (~0ull >> (64 - c2));
if (w) {
int nb = (b2 << 6) + 63 - clz(w);
return (nb << 6) + 63 - clz(v1[nb]);
}
}
if (b2) {
w = v3 & (~0ull >> (64 - b2));
if (w) {
int nb2 = 63 - clz(w);
int nb = (nb2 << 6) + 63 - clz(v2[nb2]);
return (nb << 6) + 63 - clz(v1[nb]);
}
}
return -1;
}
:::
模板
:::info[代码]
class Bitmap {
public:
ull v1[1 << 12];
ull v2[1 << 6];
ull v3;
int cnt[1 << 18];
void insert(int x) {
if (++cnt[x] != 1) return;
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1];
v1[b1] = w | (1ull << c1);
if (w) return;
int b2 = b1 >> 6,c2 = b1 & 63;
w = v2[b2];
v2[b2] = w | (1ull << c2);
if (w) return;
v3 |= 1ull << b2;
}
void erase(int x) {
if (--cnt[x]) return;
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1] & ~(1ull << c1);
v1[b1] = w;
if (w) return;
int b2 = b1 >> 6,c2 = b1 & 63;
w = v2[b2] & ~(1ull << c2);
v2[b2] = w;
if (w) return;
v3 &= ~(1ull << b2);
}
int find_min() { // 求最小值
if (v3 == 0) return -1;
int r3 = ctz(v3);
int r2 = ctz(v2[r3]);
int r1 = ctz(v1[(r3 << 6) + r2]);
return (r3 << 12) + (r2 << 6) + r1;
}
int find_max() { // 求最大值
if (v3 == 0) return -1;
int r3 = 63 - clz(v3);
int r2 = 63 - clz(v2[r3]);
int r1 = 63 - clz(v1[(r3 << 6) + r2]);
return (r3 << 12) + (r2 << 6) + r1;
}
int find_prev(int x) { // 查询<=x中第一个为1的位置
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1] & (~0ull >> (63 - c1));
if (w) return (b1 << 6) + 63 - clz(w);
int b2 = b1 >> 6,c2 = b1 & 63;
if (c2) {
w = v2[b2] & (~0ull >> (64 - c2));
if (w) {
int nb = (b2 << 6) + 63 - clz(w);
return (nb << 6) + 63 - clz(v1[nb]);
}
}
if (b2) {
w = v3 & (~0ull >> (64 - b2));
if (w) {
int nb2 = 63 - clz(w);
int nb = (nb2 << 6) + 63 - clz(v2[nb2]);
return (nb << 6) + 63 - clz(v1[nb]);
}
}
return -1;
}
int find_next(int x) { // 查询>=x中第一个为1的位置
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1] & (~0ull << c1);
if (w) return (b1 << 6) + ctz(w);
int b2 = b1 >> 6,c2 = b1 & 63;
if (c2 < 63) { // 查询同一组里b1之后的1
w = v2[b2] & (~0ull << (c2 + 1));
if (w) {
int nb = (b2 << 6) + ctz(w);
return (nb << 6) + ctz(v1[nb]);
}
}
if (b2 < 63) { // 查询更高组的1
w = v3 & (~0ull << (b2 + 1));
if (w) {
int nb2 = ctz(w);
int nb = (nb2 << 6) + ctz(v2[nb2]);
return (nb << 6) + ctz(v1[nb]);
}
}
return -1;
}
void set_0() { // 设置为全0
memset(cnt,0,sizeof(cnt));
memset(v1,0,sizeof(v1));
memset(v2,0,sizeof(v2));
v3 = 0;
}
void set_1() { // 设置为全1
fill(cnt,cnt + sizeof(cnt) / sizeof(int),1);
memset(v1,0xff,sizeof(v1));
memset(v2,0xff,sizeof(v2));
v3 = ~0ull;
}
} bitmap;
:::
四:复杂度与实测对比
复杂度
| 结构 | 插入 / 删除 | 求最值 | 前驱 / 后继 | 内存 |
| ----------------- | ------------------- | ------------------- | ------------------- | ------------------------- |
| `bool` 数组 | $O(1)$ | $O(V)$ | $O(V)$ | $V$ B |
| 裸 bitset | $O(1)$ | $O(V/64)$ | $O(V/64)$ | $V/8$ B |
| 值域分块(块 $B$) | $O(1)$ | $O(V/B+B/64)$ | 同左 | $V/8+\frac{V}{B}\cdot4$ B |
| 线段树 | $O(\log V)$ | $O(\log V)$ | $O(\log V)$ | $2V\cdot4$ B |
| 树状数组 | $O(\log V)$ | $O(\log V)$ | $O(\log V)$ | $V\cdot4$ B |
| `std::set` / PBDS | $O(\log n)$ | $O(1)$ | $O(\log n)$ | $\approx48$ B/元素 |
| **分层位图索引** | $\boldsymbol{O(\log_w V)}$ | $\boldsymbol{O(\log_w V) }$ | $\boldsymbol{O(\log_w V) }$ | $V/8$ B |
## 实测
让 deepseek 测试了一下。
### 一、写入:随机 vs 顺序 vs 等距跳跃(ms / 2.1e6 次)
| 结构 | R 随机 ins / era | S 顺序 ins / era | J 等距 ins / era |
|---|---:|---:|---:|
| **分层位图索引** | 2.6 / 2.1 | 5.6 / 4.6 | 4.6 / 4.2 |
| 裸 bitset | 1.5 / 1.8 | 3.0 / 3.6 | 1.4 / 1.5 |
| 值域分块 | 4.9 / 4.5 | 5.3 / 5.2 | 5.5 / 5.2 |
| 线段树 | 25.6 / 25.2 | 15.1 / 15.6 | 20.3 / 20.9 |
| 树状数组 | 96.6 / 95.3 | 30.7 / 27.3 | 29.4 / 29.0 |
| `std::set` | 417 / 368 | 213 / 124 | 184 / 99.7 |
| `bool` 数组 | 1.7 / 1.5 | 1.3 / 1.7 | 1.7 / 1.5 |
### 二、查询:三档数据分布(ms / 1e6 次)
**R 随机**($|S|=4096$,均匀撒开):
| 结构 | min | max | prev | next |
|---|---:|---:|---:|---:|
| **分层位图索引** | 1.9 | 6.6 | 8.2 | 9.7 |
| 裸 bitset | 2.2 | 1.8 | 11.4 | 11.1 |
| 值域分块 | 1.9 | 1.8 | 13.2 | 13.9 |
| 线段树 | 9.9 | 16.5 | 138 | 145 |
| 树状数组 | 17.5 | 14.5 | 111 | 112 |
| `std::set` | 1.5 | 2.9 | 73.4 | 64.1 |
| `bool` 数组 | 18.3 | 17.2 | 47.8 | 43.2 |
**S 稀疏等距**($|S|=64$,间隔 4096,用于压制“逐字扫”类结构):
| 结构 | min | max | prev | next |
|---|---:|---:|---:|---:|
| **分层位图索引** | 2.0 | 6.8 | 11.0 | 9.8 |
| 裸 bitset | 12.1 | 12.6 | 24.8 | 23.4 |
| 值域分块 | 1.8 | 13.4 | 27.4 | 24.8 |
| 线段树 | 8.1 | 13.6 | 110 | 98.0 |
| 树状数组 | 17.9 | 14.9 | 65.8 | 68.5 |
| `std::set` | 1.5 | 2.9 | 29.8 | 26.8 |
| `bool` 数组 | 664 | 704 | 927 | 1002 |
**E 偏心**($|S|=4096$ 全挤在 $[0,4096)$,查询全落在高端空区):
| 结构 | min | max | prev | next |
|---|---:|---:|---:|---:|
| **分层位图索引** | 3.0 | 7.3 | 6.4 | 5.9 |
| 裸 bitset | 2.5 | **1804\*** | 913 | 928 |
| 值域分块 | 2.8 | 109 | 91.6 | 67.1 |
| 线段树 | 13.4 | 22.5 | 145 | 101 |
| 树状数组 | 24.5 | 19.1 | 43.4 | 23.3 |
| `std::set` | 2.3 | 4.3 | 27.1 | 25.5 |
| `bool` 数组 | 2.5 | **114386\*** | **56057\*** | **58193\*** |
\* 表示 1.2 秒内没跑完 1e6 次,按实际完成次数折算,真实值只会更大。
# 五:例题
## 1.[P4137 Rmq Problem / mex](https://www.luogu.com.cn/problem/P4137) Rmq Problem
本题可以用莫队+一个动态维护 mex 的数据结构,那么我们可以用分层位图索引处理,只需要先将所有的节点先设置为 $1$,然后调换原来 `insert` 和 `erase`,其他操作不变。
:::info[代码]
```
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ctz __builtin_ctzll
#define clz __builtin_clzll
#ifdef _WIN32
#define getchar _getchar_nolock
#else
#define getchar getchar_unlocked
#endif
int read() {
int x=0,f=1;char chr=getchar();
while (chr<'0'||'9'<chr){if(chr=='-')f=-f;chr=getchar();}
while ('0'<=chr&&chr<='9'){x=x*10+chr-'0';chr=getchar();}
return x*f;
}
const int N = 2e5 + 10,SN = 1e3 + 10;
const ull W = 64;
const ull inf = 0xffffffffffffffff;
int n,m;
int a[N];
struct Node {
int l,r;
int id;
#define l(i) node[i].l
#define r(i) node[i].r
#define id(i) node[i].id
} node[N];
int L[SN],R[SN],block,num,pos[N];
bool cmp(const Node &a,const Node &b) {
if (pos[a.l] != pos[b.l]) return a.l < b.l;
if (pos[a.l] & 1) return a.r < b.r;
else return a.r > b.r;
}
class Bitmap {
public:
ull v1[1 << 12];
ull v2[1 << 6];
ull v3;
int cnt[1 << 18];
void insert(int x) {
if (++cnt[x] != 1) return;
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1];
v1[b1] = w | (1ull << c1);
if (w) return;
int b2 = b1 >> 6,c2 = b1 & 63;
w = v2[b2];
v2[b2] = w | (1ull << c2);
if (w) return;
v3 |= 1ull << b2;
}
void erase(int x) {
if (--cnt[x]) return;
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1] & ~(1ull << c1);
v1[b1] = w;
if (w) return;
int b2 = b1 >> 6,c2 = b1 & 63;
w = v2[b2] & ~(1ull << c2);
v2[b2] = w;
if (w) return;
v3 &= ~(1ull << b2);
}
int find_min() { // 求最小值
if (v3 == 0) return -1;
int r3 = ctz(v3);
int r2 = ctz(v2[r3]);
int r1 = ctz(v1[(r3 << 6) + r2]);
return (r3 << 12) + (r2 << 6) + r1;
}
int find_max() { // 求最大值
if (v3 == 0) return -1;
int r3 = 63 - clz(v3);
int r2 = 63 - clz(v2[r3]);
int r1 = 63 - clz(v1[(r3 << 6) + r2]);
return (r3 << 12) + (r2 << 6) + r1;
}
int find_prev(int x) { // 查询<=x中第一个为1的位置
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1] & (~0ull >> (63 - c1));
if (w) return (b1 << 6) + 63 - clz(w);
int b2 = b1 >> 6,c2 = b1 & 63;
if (c2) {
w = v2[b2] & (~0ull >> (64 - c2));
if (w) {
int nb = (b2 << 6) + 63 - clz(w);
return (nb << 6) + 63 - clz(v1[nb]);
}
}
if (b2) {
w = v3 & (~0ull >> (64 - b2));
if (w) {
int nb2 = 63 - clz(w);
int nb = (nb2 << 6) + 63 - clz(v2[nb2]);
return (nb << 6) + 63 - clz(v1[nb]);
}
}
return -1;
}
int find_next(int x) { // 查询>=x中第一个为1的位置
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1] & (~0ull << c1);
if (w) return (b1 << 6) + ctz(w);
int b2 = b1 >> 6,c2 = b1 & 63;
if (c2 < 63) { // 查询同一组里b1之后的1
w = v2[b2] & (~0ull << (c2 + 1));
if (w) {
int nb = (b2 << 6) + ctz(w);
return (nb << 6) + ctz(v1[nb]);
}
}
if (b2 < 63) { // 查询更高组的1
w = v3 & (~0ull << (b2 + 1));
if (w) {
int nb2 = ctz(w);
int nb = (nb2 << 6) + ctz(v2[nb2]);
return (nb << 6) + ctz(v1[nb]);
}
}
return -1;
}
void set_0() { // 设置为全0
memset(cnt,0,sizeof(cnt));
memset(v1,0,sizeof(v1));
memset(v2,0,sizeof(v2));
v3 = 0;
}
void set_1() { // 设置为全1
fill(cnt,cnt + sizeof(cnt) / sizeof(int),1);
memset(v1,0xff,sizeof(v1));
memset(v2,0xff,sizeof(v2));
v3 = ~0ull;
}
} bitmap;
int ans[N];
int main() {
n = read(),m = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
}
for (int i = 1; i <= m; i++) {
l(i) = read(),r(i) = read();
id(i) = i;
}
block = sqrt(n),num = n / block;
for (int i = 1; i <= num; i++) {
L[i] = R[i - 1] + 1,R[i] = R[i - 1] + block;
}
if (R[num] < n) {
num++;
L[num] = R[num - 1] + 1,R[num] = n;
}
for (int i = 1; i <= num; i++) {
for (int j = L[i]; j <= R[i]; j++) {
pos[j] = i;
}
}
sort(node + 1,node + m + 1,cmp);
bitmap.set_1();
int l = l(1),r = l(1) - 1;
for (int i = 1; i <= m; i++) {
while (r < r(i)) bitmap.erase(a[++r]);
while (l(i) < l) bitmap.erase(a[--l]);
while (r(i) < r) bitmap.insert(a[r--]);
while (l < l(i)) bitmap.insert(a[l++]);
ans[id(i)] = bitmap.find_min();
}
for (int i = 1; i <= m; i++) {
cout << ans[i] << "\n";
}
return 0;
}
```
:::
动态维护 mex 也是分层位图索引最主要的应用之一。
## 2.[P17855 [LBA-OI R6 C] 哥德巴赫猜想](https://www.luogu.com.cn/problem/P17855)
本题需要 $O(1)$ 查询前后缀,可以用分层位图索引实现,不过由于值域较大,所以要用四级位图。
:::info[代码]
```
// 思路参考https://www.luogu.com.cn/article/j80jko6t
#include<bits/stdc++.h>
using namespace std;
#define ctz __builtin_ctzll
#define clz __builtin_clzll
#define ull unsigned long long
#ifdef _WIN32
#define getchar _getchar_nolock
#else
#define getchar getchar_unlocked
#endif
int read() {
int x=0,f=1;char chr=getchar();
while (chr<'0'||'9'<chr){if(chr=='-')f=-f;chr=getchar();}
while ('0'<=chr&&chr<='9'){x=x*10+chr-'0';chr=getchar();}
return x*f;
}
#define ll long long
const int N = 1e6 + 10,Q = 2e6 + 10;
int ver[N],nxt[N],head[N],tot = 0;
void add(int x,int y) {
ver[++tot] = y,nxt[tot] = head[x],head[x] = tot;
}
int n,q;
int fa[N],a[N];
static const int V = 2e6 + 10;
static const int N1 = (V + 63) >> 6; // v1 字数
static const int N2 = (N1 + 63) >> 6; // v2 字数
static const int N3 = (N2 + 63) >> 6; // v3 字数
struct Bitmap4 {
ull v1[N1];
ull v2[N2];
ull v3[N3];
ull v4;
int cnt[V];
void insert(int x) {
if (++cnt[x] != 1) return;
int b1 = x >> 6, c1 = x & 63;
ull w = v1[b1];
v1[b1] = w | (1ull << c1);
if (w) return;
int b2 = b1 >> 6, c2 = b1 & 63;
w = v2[b2];
v2[b2] = w | (1ull << c2);
if (w) return;
int b3 = b2 >> 6, c3 = b2 & 63;
w = v3[b3];
v3[b3] = w | (1ull << c3);
if (w) return;
v4 |= 1ull << b3;
}
void erase(int x) {
if (--cnt[x]) return;
int b1 = x >> 6, c1 = x & 63;
ull w = v1[b1] & ~(1ull << c1);
v1[b1] = w;
if (w) return;
int b2 = b1 >> 6, c2 = b1 & 63;
w = v2[b2] & ~(1ull << c2);
v2[b2] = w;
if (w) return;
int b3 = b2 >> 6, c3 = b2 & 63;
w = v3[b3] & ~(1ull << c3);
v3[b3] = w;
if (w) return;
v4 &= ~(1ull << b3);
}
int find_min() {
if (!v4) return -1;
int r4 = ctz(v4);
int r3 = ctz(v3[r4]);
int r2 = ctz(v2[(r4 << 6) + r3]);
int r1 = ctz(v1[(r4 << 12) + (r3 << 6) + r2]);
return (r4 << 18) + (r3 << 12) + (r2 << 6) + r1;
}
int find_max() {
if (!v4) return -1;
int r4 = 63 - clz(v4);
int r3 = 63 - clz(v3[r4]);
int r2 = 63 - clz(v2[(r4 << 6) + r3]);
int r1 = 63 - clz(v1[(r4 << 12) + (r3 << 6) + r2]);
return (r4 << 18) + (r3 << 12) + (r2 << 6) + r1;
}
int find_prev(int x) {
if (x < 0) return -1;
int b1 = x >> 6, c1 = x & 63;
ull w = v1[b1] & (~0ull >> (63 - c1));
if (w) return (b1 << 6) + 63 - clz(w);
int b2 = b1 >> 6, c2 = b1 & 63;
if (c2) {
w = v2[b2] & (~0ull >> (64 - c2));
if (w) { int nb = (b2 << 6) + 63 - clz(w); return (nb << 6) + 63 - clz(v1[nb]); }
}
int b3 = b2 >> 6, c3 = b2 & 63;
if (c3) {
w = v3[b3] & (~0ull >> (64 - c3));
if (w) {
int nb2 = (b3 << 6) + 63 - clz(w);
int nb1 = (nb2 << 6) + 63 - clz(v2[nb2]);
return (nb1 << 6) + 63 - clz(v1[nb1]);
}
}
if (b3) {
w = v4 & (~0ull >> (64 - b3));
if (w) {
int nb3 = 63 - clz(w);
int nb2 = (nb3 << 6) + 63 - clz(v3[nb3]);
int nb1 = (nb2 << 6) + 63 - clz(v2[nb2]);
return (nb1 << 6) + 63 - clz(v1[nb1]);
}
}
return -1;
}
int find_next(int x) {
int b1 = x >> 6, c1 = x & 63;
ull w = v1[b1] & (~0ull << c1);
if (w) return (b1 << 6) + ctz(w);
int b2 = b1 >> 6, c2 = b1 & 63;
if (c2 < 63) {
w = v2[b2] & (~0ull << (c2 + 1));
if (w) { int nb = (b2 << 6) + ctz(w); return (nb << 6) + ctz(v1[nb]); }
}
int b3 = b2 >> 6, c3 = b2 & 63;
if (c3 < 63) {
w = v3[b3] & (~0ull << (c3 + 1));
if (w) {
int nb2 = (b3 << 6) + ctz(w);
int nb1 = (nb2 << 6) + ctz(v2[nb2]);
return (nb1 << 6) + ctz(v1[nb1]);
}
}
if (b3 < 63) {
w = v4 & (~0ull << (b3 + 1));
if (w) {
int nb3 = ctz(w);
int nb2 = (nb3 << 6) + ctz(v3[nb3]);
int nb1 = (nb2 << 6) + ctz(v2[nb2]);
return (nb1 << 6) + ctz(v1[nb1]);
}
}
return -1;
}
void set_0() {
memset(cnt,0,sizeof(cnt));
memset(v1, 0, sizeof(v1));
memset(v2, 0, sizeof(v2));
memset(v3, 0, sizeof(v3));
v4 = 0;
}
void set_1() {
fill(cnt,cnt + sizeof(cnt) / sizeof(int),1);
memset(v1, 0xff, sizeof(v1));
memset(v2, 0xff, sizeof(v2));
memset(v3, 0xff, sizeof(v3));
v4 = ~0ull;
}
} bitmap[2];
int op[Q];
int ans[Q];
int L[N],R[N],num;
int val[Q];
vector<int> tim[N];
void dfs(int x) {
L[x] = num + 1;
for (auto i : tim[x]) {
num++;
val[num] = i;
}
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
dfs(y);
}
R[x] = num;
}
int p[N];
int main() {
n = read(),q = read();
for (int i = 1; i <= n; i++) {
fa[i] = read();
if (fa[i]) {
add(fa[i],i);
}
p[i] = i;
}
for (int i = 1; i <= n; i++) {
a[i] = read();
}
for (int i = 1; i <= q; i++) {
op[i] = read();
if (op[i] == 1) {
op[i] = read();
tim[op[i]].push_back(i);
}
else {
op[i] = 0;
bitmap[1].insert(i);
}
}
for (int i = 1; i <= n; i++) {
if (fa[i] == 0) {
dfs(i);
}
}
bitmap[0].set_1();
sort(p + 1,p + n + 1,[](int x,int y) {return a[x] > a[y];});
// cout << "p = ";for (int i = 1; i <= n; i++) cout << p[i] << " \n"[i == n];
// cout << "L = ";for (int i = 1; i <= n; i++) cout << L[i] << " \n"[i == n];
// cout << "R = ";for (int i = 1; i <= n; i++) cout << R[i] << " \n"[i == n];
// cout << "val = ";for (int i = 1; i <= num; i++) cout << val[i] << " \n"[i == num];
for (int i = 1; i <= n; i++) {
// cout << "i = " << i << " p[i] = " << p[i] << "\n";
if (L[p[i]] > R[p[i]]) continue;
int x = bitmap[0].find_prev(R[p[i]]);
while (L[p[i]] <= x) {
int y = bitmap[1].find_next(val[x]);
// cout << "x = " << x << " val[x] = " << val[x] << " y = " << y << "\n";
if (y == -1) {
bitmap[0].erase(x);
}
else {
ans[y] = a[p[i]];
bitmap[1].erase(y);
}
x = bitmap[0].find_prev(x - 1);
// system("pause");
}
}
ll val = 0;
int k = 0;
for (int i = 1; i <= q; i++) {
if (op[i] == 0) {
// cout << "i = " << i << " ans[i] = " << ans[i] << "\n";
val ^= (ll)(++k) * ans[i];
}
}
cout << val << "\n";
return 0;
}
```
:::
## 3.[P4145 上帝造题的七分钟 2 / 花神游历各国](https://www.luogu.com.cn/problem/P4145)
本题需要维护给定区间中 $a_i>1$ 的位置,标准解法是用并查集维护下一个符合的位置,显然我们也可以用分层位图索引来处理。
:::info[代码]
```
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define clz __builtin_clzll
#define ctz __builtin_ctzll
#ifdef _WIN32
#define getchar _getchar_nolock
#else
#define getchar getchar_unlocked
#endif
int read() {
int x=0,f=1;char chr=getchar();
while (chr<'0'||'9'<chr){if(chr=='-')f=-f;chr=getchar();}
while ('0'<=chr&&chr<='9'){x=x*10+chr-'0';chr=getchar();}
return x*f;
}
ull readll() {
ull x=0,f=1;char chr=getchar();
while (chr<'0'||'9'<chr){if(chr=='-')f=-f;chr=getchar();}
while ('0'<=chr&&chr<='9'){x=x*10+chr-'0';chr=getchar();}
return x*f;
}
const int N = 1e5 + 10;
const int N1 = (N + 63) >> 6;
const int N2 = (N1 + 63) >> 6;
int n,m;
ull a[N];
ull c[N];
int lowbit(int x) {
return x & (-x);
}
ull v1[N1],v2[N2],v3;
void insert(int x) {
int b1 = x >> 6,c1 = x & 63;
v1[b1] |= 1ull << c1;
if (v1[b1] != (1ull << c1)) return;
int b2 = b1 >> 6,c2 = b1 & 63;
v2[b2] |= 1ull << c2;
if (v2[b2] != (1ull << c2)) return;
v3 |= 1ull << b2;
}
void erase(int x) {
int b1 = x >> 6,c1 = x & 63;
v1[b1] &= ~(1ull << c1);
if (v1[b1]) return;
int b2 = b1 >> 6,c2 = b1 & 63;
v2[b2] &= ~(1ull << c2);
if (v2[b2]) return;
v3 &= ~(1ull << b2);
}
int find_next(int x) {
int b1 = x >> 6,c1 = x & 63;
ull w = v1[b1] & (~0ull << c1);
if (w) return (b1 << 6) + ctz(w);
int b2 = b1 >> 6,c2 = b1 & 63;
if (c2 < 63) {
w = v2[b2] & (~0ull << (c2 + 1));
if (w) {
int nb = (b2 << 6) + ctz(w);
return (nb << 6) + ctz(v1[nb]);
}
}
if (b2 < 63) {
w = v3 & (~0ull << (b2 + 1));
if (w) {
int nb2 = ctz(w);
int nb = (nb2 << 6) + ctz(v2[nb2]);
return (nb << 6) + ctz(v1[nb]);
}
}
return -1;
}
void add(int x,ull v) {
for (; x <= n; x += lowbit(x)) {
c[x] += v;
}
}
ull sum(int x) {
ull ans = 0;
for (; x; x -= lowbit(x)) {
ans += c[x];
}
return ans;
}
int main() {
n = read();
for (int i = 1; i <= n; i++) {
a[i] = readll();
c[i] += a[i];
if (a[i] > 1) {
insert(i);
}
int j = i + lowbit(i);
if (j <= n) {
c[j] += c[i];
}
}
insert(n + 1);
m = read();
for (int i = 1; i <= m; i++) {
int op = read(),l = read(),r = read();
if (l > r) swap(l,r);
if (op == 0) {
int x = find_next(l);
while (x <= r) {
// cout << "x = " << x << " c[x] = " << sum(x) - sum(x - 1) << "\n";
ull val = sqrt(a[x]);
add(x,val - a[x]);
// cout << "x = " << x << " c[x] = " << sum(x) - sum(x - 1) << "\n";
a[x] = val;
if (a[x] == 1) erase(x);
x = find_next(x + 1);
}
}
else {
cout << sum(r) - sum(l - 1) << "\n";
}
}
return 0;
}
```
:::
# 后话
事情的起因是我在解决 [哥德巴赫猜想](https://www.luogu.com.cn/problem/P17855) 的时候遇到了需要支持将 $a_x$ 变为 $1$ 和查询 $x$ 左侧第一个 $0$ 的数据结构,显然这可以用并查集 $O(n\alpha(n))$ 实现,但我当时以为这是 $O(n\log n)$ 的,遂问 deepseek 有没有 $O(n)$ 的算法,于是她就教了我以上的数据结构。
***
upd at 2026-11-18。
最开始写时间复杂度是 $O(1)$ 一方面是为了吸引读者兴趣,另一方面是在 $10^9$ 的范围最多只能开五层,所以将其近似为了 $O(1)$,经评论区指正,现在已统一修改为 $O(\log_w V)$。
本人之前不知道压位 trie,经评论区指出两者一样,但分层位图索引(Hierarchical Bitmap Index)的名称至少可以追溯 2003 年,而压位 trie 的名称据我所知出自 2021 国家集训队论文钱易的《浅谈亚 log 数据结构在 OI 中的应用》,所以我认为我这样写是没有任何问题的。