块状链表详解

引入

块状链表，顾名思义，就是把分块和链表结合起来的神奇数据结构。

• 分块区间操作复杂度优秀，但是不能支持 插入/删除 操作。

• 链表单点插入删除复杂度优秀，但是不能支持大规模的区间操作。

但是两者相结合，就会变得非常无敌。

块状链表思想

块状链表的实现原理根本上就是保证每个块的大小稳定在 \(\sqrt{n}\) 级别，从而保证块数也为根号级别。但是插入数据之后，可能会出现某个快过大的情况。当块长 \(> 2 \sqrt{n}\) 时，可以将块分裂成两个，保证每块大小稳定在 \([\sqrt{n}, 2\sqrt{n}]\)。这样分裂的复杂度是单根号的。

这样保证了块数为根号级别，定位一个数的位置也可以在 \(O(\sqrt n)\) 复杂度内解决。只要能定位数所在的位置，就可以用 \(O(1)\) 复杂度完成插入和删除，其他操作都跟分块复杂度相同。

块状链表如何维护数据

拿 Luogu 普通平衡树模板 做例题。

要支持在 \(O(\sqrt n)\) 复杂度内维护一个有序序列。

首先需要建一个双链表（某些题可以单链表），作为外层数据结构。

然后再每个链表里面维护一个小链表（可以用 vector 实现），来维护当前块。另外，由于后续操作写成 (p -> vector).lower_bound((p -> vector).begin(), (p -> vector).end(), x) 这样的形式不是很美观，也可以在块链类内部提前封装类似函数。

• 块状链表定义形式

struct node { // 构建块状链表类
    node *next, *pre;
    vector<int> v;
    node() { next = pre = NULL; }
    void insert(int x) { v.emplace_back(x); }
    int vsize() { return v.size(); }
    int back() { return v[v.size() - 1]; }
    int front() { return v[0]; }
    vector<int>::iterator vbegin() { return v.begin(); }
    vector<int>::iterator vend() { return v.end(); }
    vector<int>::iterator lower(int x) { return lower_bound(v.begin(), v.end(), x); }
    vector<int>::iterator upper(int x) { return upper_bound(v.begin(), v.end(), x); }
}*head, pool[1010], *idx;

我拿指针实现的。当然用 vector 更简便。

• 块的分裂

void split(node *p) { // 将大块分裂成两个小块，S为每块的长度阈值
    node *q = new(idx ++ )node();
    q -> next = p -> next; if (q -> next) q -> next -> pre = q;
    p -> next = q, q -> pre = p;
    rop(i, S, p -> vsize()) q -> insert((p -> v)[i]);
    (p -> v).erase(p -> vbegin() + S, p -> vend());
}

对于普通平衡树这题来说，我们维护的序列是有序的。因此可以直接按照权值来查找。定位当前数在那个块也非常容易。

• 定位

node *find(int x) { // 找到 x 所在块
    for (node *p = head; p; p = p -> next)
        if (p -> back() >= x) return p;
}

剩下的操作就很套路了。就不再赘述了。

复杂度当然是 \(O(n \sqrt n)\)，跑的好像比平衡树快一点。

代码示例

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>

#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
#define dop(i, a, b) for (int i = (a); i > (b); i -- )

using namespace std;

const int INF = 2e9;
int n, S;

struct node { // 构建块状链表类
    node *next, *pre;
    vector<int> v;
    node() { next = pre = NULL; }
    void insert(int x) { v.emplace_back(x); }
    int vsize() { return v.size(); }
    int back() { return v[v.size() - 1]; }
    int front() { return v[0]; }
    vector<int>::iterator vbegin() { return v.begin(); }
    vector<int>::iterator vend() { return v.end(); }
    vector<int>::iterator lower(int x) { return lower_bound(v.begin(), v.end(), x); }
    vector<int>::iterator upper(int x) { return upper_bound(v.begin(), v.end(), x); }
}*head, pool[1010], *idx;

node *find(int x) { // 找到 x 所在块
    for (node *p = head; p; p = p -> next)
        if (p -> back() >= x) return p;
}
void split(node *p) { // 将大块分裂成两个小块
    node *q = new(idx ++ )node();
    q -> next = p -> next; if (q -> next) q -> next -> pre = q;
    p -> next = q, q -> pre = p;
    rop(i, S, p -> vsize()) q -> insert((p -> v)[i]);
    (p -> v).erase(p -> vbegin() + S, p -> vend());
}
void insert(int x) { // 插入操作
    node *p = find(x); (p -> v).emplace(p -> lower(x), x);
    if (p -> vsize() >= 2 * S) split(p);
}
void remove(int x) { // 移除数 x 
    node *p = find(x); // 找到 x 的位置
    (p -> v).erase(p -> lower(x));
    if (p -> vsize() == 0) { // 如果当前块空了
        if (p == head) { // 如果是头结点，更新头结点
            head = p -> next, head -> pre = NULL;
            return;
        }
        // 更新与下一个节点的关系
        p -> pre -> next = p -> next;
        p -> next -> pre = p -> pre;
        p -> next = p -> pre = NULL;
    }
}
int get_rank(int x) { // 根据权值找排名
    int cnt = 0;
    for (node *now = head; now; now = now -> next) {
        if (now -> back() >= x) {
            cnt += (now -> lower(x)) - (now -> vbegin()); return cnt + 1;
        }
        else cnt += now -> vsize();
    }
    return cnt + 1;
}
int get_kth(int k) { // 根据排名找权值
    int cnt = 0;
    for (node *now = head; now; now = now -> next) {
        if (cnt + now -> vsize() < k) {
            cnt += now -> vsize(); continue;
        }
        return (now -> v)[k - cnt - 1];
    }
}
int get_pre(int x) { // 找前驱
    node *p = find(x);
    if (p -> front() >= x) return p -> pre -> back();
    return *((p -> lower(x)) - 1);
}
int get_next(int x) { // 找后继
    node *p = find(x);
    if (p -> back() == x) return *(p -> next -> upper(x));
    return *(p -> upper(x));
}

int main() {
    idx = pool;
    scanf("%d", &n);
    S = (int)sqrt(n); // 块长
	head = new(idx ++ )node();
    (head -> v).emplace_back(INF);

	while (n -- ) {
		int op, x;
		scanf("%d%d", &op, &x);
		if (op == 1) insert(x);
		if (op == 2) remove(x);
		if (op == 3) printf("%d\n", get_rank(x));
		if (op == 4) printf("%d\n", get_kth(x));
		if (op == 5) printf("%d\n", get_pre(x));
		if (op == 6) printf("%d\n", get_next(x));
	}

	return 0;
}

另外看在我写了这么毒瘤的数据结构的份上，点一个免费的赞吧！！（块状链表真的不好写）