塊狀鏈表

./images/kuaizhuanglianbiao.png

塊狀鏈表大概就長這樣……

不難發現塊狀鏈表就是一個鏈表，每個節點指向一個數組。我們把原來長度為 n 的數組分為 \(\sqrt{n}\) 個節點，每個節點對應的數組大小為 \(\sqrt{n}\)。所以我們這麼定義結構體，代碼見下。其中 sqn 表示 sqrt(n) 即 \(\sqrt{n}\)，pb 表示 push_back，即在這個 node 中加入一個元素。

實現

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; }
};

塊狀鏈表應該至少支持：分裂、插入、查找。什麼是分裂？分裂就是分裂一個 node，變成兩個小的 node，以保證每個 node 的大小都接近 \(\sqrt{n}\)（否則可能退化成普通數組）。當一個 node 的大小超過 \(2\times \sqrt{n}\) 時執行分裂操作。

分裂操作怎麼做呢？先新建一個節點，再把被分裂的節點的後 \(\sqrt{n}\) 個值 copy 到新節點，然後把被分裂的節點的後 \(\sqrt{n}\) 個值刪掉（size--），最後把新節點插入到被分裂節點的後面即可。

塊狀鏈表的所有操作的複雜度都是 \(\sqrt{n}\) 的。

還有一個要説的。隨着元素的插入（或刪除），\(n\) 會變，\(\sqrt{n}\) 也會變。這樣塊的大小就會變化，我們難道還要每次維護塊的大小？

其實不然，把 \(\sqrt{n}\) 設置為一個定值即可。比如題目給的範圍是 \(10^6\)，那麼 \(\sqrt{n}\) 就設置為大小為 \(10^3\) 的常量，不用更改它。

list<vector<char> > orz_list;

STL 中的 `rope`

導入

STL 中的 rope 也起到塊狀鏈表的作用，它採用可持久化平衡樹實現，可完成隨機訪問和插入、刪除元素的操作。

由於 rope 並不是真正的用塊狀鏈表來實現，所以它的時間複雜度並不等同於塊狀鏈表，而是相當於可持久化平衡樹的複雜度（即 \(O(\log n)\)）。

可以使用如下方法來引入：

#include <ext/rope>
using namespace __gnu_cxx;

關於雙下劃線開頭的庫函數

OI 中，關於能否使用雙下劃線開頭的庫函數曾經一直不確定，2021 年 CCF 發佈的關於 NOI 系列活動中編程語言使用限制的補充説明中提到「允許使用以下劃線開頭的庫函數或宏，但具有明確禁止操作的庫函數和宏除外」。故 rope 目前可以在 OI 中正常使用。

基本操作

操作	作用
`rope <int > a`	初始化 `rope`（與 `vector` 等容器很相似）
`a.push_back(x)`	在 `a` 的末尾添加元素 `x`
`a.insert(pos, x)`	在 `a` 的 `pos` 個位置添加元素 `x`
`a.erase(pos, x)`	在 `a` 的 `pos` 個位置刪除 `x` 個元素
`a.at(x)` 或 `a[x]`	訪問 `a` 的第 `x` 個元素
`a.length()` 或 `a.size()`	獲取 `a` 的大小

例題

POJ2887 Big String

題解：很簡單的模板題。代碼如下：

#include <cctype>
#include <cstdio>
#include <cstring>
using namespace std;
static 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; }
}* head = NULL;

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

void readch(char& ch) {  // 读入字符
  do ch = getchar();
  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() {
  scanf("%s %d", 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')
      scanf("%d", &k), printf("%c\n", query(k));
    else
      readch(a), scanf("%d", &k), insert(a, k);
  }
  return 0;
}

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：HeRaNO, konnyakuxzy, littlefrog
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

塊狀鏈表

STL 中的 rope

導入

基本操作

例題

STL 中的 `rope`