Block List

A block list looks roughly like this...

A block list is simply a linked list in which each node points to an array. We divide the original array of length n into $\sqrt{n}$ nodes, with an array of size $\sqrt{n}$ corresponding to each node. Thus we define the following structure; the code is shown below. Here sqn denotes sqrt(n), namely $\sqrt{n}$, and pb denotes push_back, which adds an element to this 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; }
};

A block list should support at least splitting, insertion, and lookup. What is splitting? Splitting divides one node into two smaller node objects, keeping the size of every node close to $\sqrt{n}$ (otherwise it may degenerate into an ordinary array). Perform a split when a node exceeds $2\times \sqrt{n}$ elements.

How is splitting performed? First create a new node, then copy the last $\sqrt{n}$ values of the node being split into the new node, delete those last $\sqrt{n}$ values from the original node (size--), and finally insert the new node after the original node.

Every operation on a block list has complexity $\sqrt{n}$.

There is one more issue. As elements are inserted or deleted, $n$ changes, and so does $\sqrt{n}$. The block size would therefore change as well; must we maintain the block size every time?

In fact, no. We can set $\sqrt{n}$ to a fixed value. For example, if the limit in the problem is $10^6$, set $\sqrt{n}$ to a constant of size $10^3$ and do not change it.

list<vector<char>> orz_list;

rope in libstdc++

Import

The rope in libstdc++ also serves the purpose of a block list. It uses a persistent balanced tree and supports random access as well as insertion and deletion.

Since rope is not actually implemented as a block list, its time complexity is not the same as that of a block list; instead, it is the complexity of a persistent balanced tree, namely $O(\log n)$.

It can be imported as follows:

#include <ext/rope>
using namespace __gnu_cxx;

Basic operations

Examples

POJ2887 Big String

Solution: This is a simple template problem. The code is as follows:

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

struct node {  // define the block 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 a 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) {  // insert an element; use the linked list model
  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;
}