常数访问块状链表(省流：带插分块)

· · 算法·理论

前言

因为长度是严格的，没有块链的许多优良性质，所以适用范围不广。

推荐阅读：块状链表，分块。

原理

:::info[例题]{open} 有数组 a，最初为空。在线地实现以下操作：

  1. 求 a_i。
  2. 将 a_i 改为 x。
  3. 在 a_i 前插入 x。
    如果 i \ge |a|，则表示是从末尾插入。
  4. 删除 a_i。

下标从 0 开始，操作数量 m \le 10^5。 :::

实际上就是三个操作：访问，插入，删除。访问可以返回引用，实现操作 1,2。

我们将数组分为若干个长度相等的块，每个块用 deque 维护。
为了简单，做以下约定：

vector<deque<int>> a {{}}; // 开始要有一个块

由于我们知道了第 i 个元素的位置，访问自然可以做到 O(1)。 

int& get(int p) {
  return a[p / B][p % B];
}

通过类似的方式，插入、删除时易找到元素位置。可是，如何维护长度相等的性质呢？

插入

插入一个元素到对应块后，它的长度可能是 B + 1。

插入平衡（块 i）

  1. 如果 i 是最后一个块，将末尾元素分裂为新的块。
  2. 否则，将末尾元素移动到块 i+1 的开头。
    如果块 i+1 为 B+1 个元素，对 i+1 递归执行平衡操作。

void ins(int p, int x) {
  int i = p / B;
  a[i].insert(a[i].begin() + p % B, x);
  // 平衡
  for (int e = a.size(); i < e; ++i) {
    if (i == int(a.size() - 1))
      if(a[i].size() > B) a.emplace_back();
      else break;
    a[i + 1].push_front(a[i].back());
    a[i].pop_back();
  }
}

删除

删除一个元素后，非末尾块 i 的长度可能是 B - 1。
此时，将块 i+1 的开头移动到块 i 的末尾。
如果块 i+1 是非末尾块且长度为 B - 1，对下一个块递归执行。

void del(int p) {
  int i = p / B;
  a[i].erase(a[i].begin() + p % B);
  // 平衡
  for (int e = a.size() - 1; i < e; ++i) {
    a[i].push_back(a[i + 1].front());
    a[i + 1].pop_front();
  }
}

实现

#include <bits/stdc++.h>
#define fo(i,l,r) for(int i=(l),E##i=(r);i<=E##i;++i)
#define N 100005
#define B 350
using namespace std;

struct Arr {
  vector<deque<int>> a {{}}; // 预先设置一个块

  int& get(int p) {
    return a[p / B][p % B];
  }

  void ins(int p, int x) {
    int i = p / B;
    a[i].insert(a[i].begin() + p % B, x);
    // 平衡
    for (int e = a.size(); i < e; ++i) {
      if (i == int(a.size() - 1))
        if(a[i].size() > B) a.emplace_back();
        else break;
      a[i + 1].push_front(a[i].back());
      a[i].pop_back();
    }
  }

  void del(int p) {
    int i = p / B;
    a[i].erase(a[i].begin() + p % B);
    // 平衡
    for (int e = a.size() - 1; i < e; ++i) {
      a[i].push_back(a[i + 1].front());
      a[i + 1].pop_front();
    }
  }
};

//int test() {
//  Arr a;
//  fo (i, 0, 799) a.ins(0, i);
//  fo (i, 1, 20) a.del(20);
//  fo (i, 1, 20) a.del(720);
//  fo (i, 0, 759) cout << a.get(i) << endl;
//}

// 1 询问 2 修改 3 插入 4 删除
int main() {
  int m, op, p, x;
  Arr a;
  cin >> m;
  up (i, 1, m) {
    cin >> op >> p;
    switch (op) {
    case 1: cout << a.get(p - 1) << endl; break;
    case 2: cin >> x; a.get(p - 1) = x; break;
    case 3: cin >> x; a.ins(p - 1, x); break;
    case 4: a.del(p - 1);
    }
  }
}

后记

分裂合并明天不用来了。舒服。

关于可持久化的尝试

在写可持久化块状链表：
可持久化块状数组（分块可持久化）

每个版本维护一个各块长度前缀和的数组（其实就是块头的索引），似乎也可以做到 O(\log n) 的随机访问，而且好写（逃）

发现使用哈希表记录每个索引对应的块也可以，但是可持久化哈希表又是另一个问题。

以上。