浅谈分层位图索引:一种 O(\log_w V) 求前驱和后继的算法

· · 算法·理论

分层位图索引:一种 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_w V) 修改和 O(\log_w V) 查询。

二:结构

这里我们以 V = 2^{18} = 262144 \approx 2.5\times 10^5 举例,这也是实践中最常用的,当然如果对于更大的值域我们只需要建四层位图即可。

三:实现

插入一个元素

只需要从下往上逐层更新。 :::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 中的应用》,所以我认为我这样写是没有任何问题的。