块状链表详解：原理、实现与应用

块状链表详解：原理、实现与应用

块状链表（Block List）是一种高效的数据结构，结合了链表和数组的优点，特别适合处理大规模数据的插入、删除和查询操作。本文将详细介绍块状链表的基本概念、实现方法以及在算法竞赛中的应用。

块状链表的基本思想是将一个长数组分割成多个块，每个块用一个链表节点表示，节点内部是一个固定大小的数组。这种结构可以有效平衡随机访问和插入/删除操作的效率。

块状链表的实现

块状链表应该至少支持：分裂、插入、查找。 什么是分裂？分裂就是分裂一个
node
，变成两个小的
node
，以保证每个
node
的大小都接近（否则可能退化成普通数组）。当一个
node
的大小超过时执行分裂操作。
分裂操作怎么做呢？先新建一个节点，再把被分裂的节点的后个值
copy
到新节点，然后把被分裂的节点的后个值删掉（
size--
），最后把新节点插入到被分裂节点的后面即可。
块状链表的所有操作的复杂度都是的。
还有一个要说的。 随着元素的插入（或删除），会变，也会变。这样块的大小就会变化，我们难道还要每次维护块的大小？
其实不然，把设置为一个定值即可。比如题目给的范围是，那么就设置为大小为的常量，不用更改它。
1 list<vector>orz_list;

结构体定义

struct node {
    node* nxt;
    int size;
    char d[(sqn << 1) + 5];
    node() {
        size = 0, nxt = NULL;
        memset(d, 0, sizeof(d));
    }
    void pb(char c) {
        d[size++] = c;
    }
};

基本操作

• 分裂操作：当一个节点的大小超过预设阈值时，需要将其分裂成两个节点，以保持每个节点的大小接近。
• 插入操作：在指定位置插入元素，可能需要更新多个节点。
• 查找操作：通过遍历链表和数组索引实现元素查找。

STL中的rope容器

STL中的rope容器也起到块状链表的作用，它采用可持久化平衡树实现，可完成随机访问和插入、删除元素的操作。虽然rope并不是真正的用块状链表来实现，但其功能与块状链表类似，时间复杂度相当于可持久化平衡树的复杂度（即O(log n)）。

基本操作

例题：POJ2887 Big String

这是一道经典的块状链表应用题目，主要考察块状链表的插入和查询操作。以下是完整的代码实现：

#include <cctype>
#include <cstring>
#include <iostream>
using namespace std;

const int sqn = 1e3;

struct node {
    node* nxt;
    int size;
    char d[(sqn << 1) + 5];
    node() {
        size = 0, nxt = NULL;
    }
    void pb(char c) {
        d[size++] = c;
    }
};

char inits[(int)1e6 + 5];
int llen, q;

void readch(char& ch) {
    do cin >> ch;
    while (!isalpha(ch));
}

void check(node* p) {
    if (p->size >= (sqn << 1)) {
        node* q = new node;
        for (int i = sqn; i < p->size; i++)
            q->pb(p->d[i]);
        p->size = sqn, q->nxt = p->nxt, p->nxt = q;
    }
}

void insert(char c, int pos) {
    node* p = head;
    int tot, cnt;
    if (pos > llen++) {
        while (p->nxt != NULL)
            p = p->nxt;
        p->pb(c), check(p);
        return;
    }
    for (tot = head->size; p != NULL && tot < pos; p = p->nxt, tot += p->size);
    tot -= p->size, cnt = pos - tot - 1;
    for (int i = p->size - 1; i >= cnt; i--)
        p->d[i + 1] = p->d[i];
    p->d[cnt] = c, p->size++;
    check(p);
}

char query(int pos) {
    node* p;
    int tot;
    for (p = head, tot = head->size; p != NULL && tot < pos; p = p->nxt, tot += p->size);
    tot -= p->size;
    return p->d[pos - tot - 1];
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> inits >> q;
    llen = strlen(inits);
    node* p = new node;
    head = p;
    for (int i = 0; i < llen; i++) {
        if (i % sqn == 0 && i)
            p->nxt = new node, p = p->nxt;
        p->pb(inits[i]);
    }
    char a;
    int k;
    while (q--) {
        readch(a);
        if (a == 'Q')
            cin >> k, cout << query(k) << '\n';
        else
            readch(a), cin >> k, insert(a, k);
    }
    return 0;
}

通过这个例子，我们可以看到块状链表在处理大规模字符串操作时的高效性。它结合了链表的插入优势和数组的随机访问优势，是一种非常实用的数据结构。