Block List

./images/kuaizhuanglianbiao.png

A block list roughly looks like this...

It's not hard to see that a block list is essentially a linked list, where each node points to an array. We divide the original array of length \(n\) into \(\sqrt{n}\) nodes, each node corresponding to an array of size \(\sqrt{n}\). Thus, we define the structure as follows, with the code shown below. Here, sqn represents sqrt(n), i.e., \(\sqrt{n}\), and pb stands for push_back, meaning adding an element to this node.

Implementation

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

A block list should support at least: splitting, insertion, and searching. What is splitting? Splitting is dividing a node into two smaller nodes to ensure each node's size remains close to \(\sqrt{n}\) (otherwise, it might degenerate into a regular array). When a node's size exceeds \(2 \times \sqrt{n}\), a split operation is performed.

How is the split operation done? First, create a new node, then copy the last \(\sqrt{n}\) values from the node being split to the new node. Next, delete the last \(\sqrt{n}\) values from the node being split (size--). Finally, insert the new node after the node being split.

All operations on a block list have a complexity of \(\sqrt{n}\).

One more thing to mention. As elements are inserted (or deleted), \(n\) changes, and so does \(\sqrt{n}\). This means the block size would change. Do we really need to maintain the block size every time?

Actually, no. We can set \(\sqrt{n}\) as a fixed value. For example, if the problem's range is \(10^6\), then set \(\sqrt{n}\) as a constant of size \(10^3\), and there's no need to change it.

list<vector<char>> orz_list;

`rope` in STL

Import

The rope in STL also serves as a block list. It is implemented using a persistent balanced tree and supports random access, insertion, and deletion of elements.

Since rope is not truly implemented as a block list, its time complexity is not equivalent to that of a block list but rather to that of a persistent balanced tree (i.e., \(O(\log n)\)).

It can be imported as follows:

#include <ext/rope>
using namespace __gnu_cxx;

About Library Functions Starting with Double Underscores

In OI, the permissibility of using library functions starting with double underscores was once uncertain. The Supplementary Explanation on Programming Language Usage Restrictions in NOI Series Activities released by CCF in 2021 states: "The use of library functions or macros starting with an underscore is allowed, except for those with explicitly prohibited operations." Therefore, rope can currently be used normally in OI.

Basic Operations

Operation	Effect
`rope <int > a`	Initialize a `rope` (similar to containers like `vector`)
`a.push_back(x)`	Add element `x` to the end of `a`
`a.insert(pos, x)`	Insert element `x` at the `pos`-th position of `a`
`a.erase(pos, x)`	Delete `x` elements starting from the `pos`-th position of `a`
`a.at(x)` or `a[x]`	Access the `x`-th element of `a`
`a.length()` or `a.size()`	Get the size of `a`

Example Problem

POJ2887 Big String

Solution: A very simple template problem. The code is as follows:

#include <cctype>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int sqn = 1e3;

struct node {  // Define block linked list
  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) {  // Read character
  do cin >> ch;
  while (!isalpha(ch));
}

void check(node* p) {  // Check, remember to split
  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) {  // Element insertion, understand via linked list
  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) {  // Query
  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;
}

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

Block List

rope in STL

Import

Basic Operations

Example Problem

`rope` in STL