一、概念：把链表「分块」
Mermaid · 渲染中（下方为源码）
graph LR A[块状链表] --> B[块内: 数组] A --> C[块间: 指针] B --> D[定位 O(√n)] C --> D
普通链表在任意位置插入 / 删除 / 按索引访问都是 O(n)。块状链表把链表按**块（block）**组织：每个块内用数组存若干元素，块与块之间仍用指针相连。约定每块大小不超过 S = ⌈√n⌉。
这样，定位第 k 个元素只需先 O(√n) 找到所在块，再 O(√n) 在块内定位——总复杂度 O(√n)，而空间仍是线性的。
二、核心操作
| 操作 | 步骤 | 复杂度 |
|---|---|---|
| 定位 locate(k) | 顺序遍历块累加长度，找到第 k 个元素所在块与块内偏移 | O(√n) |
| 插入 insert(k, v) | 定位后在块内 splice 插入；若块超 S，从中点分裂成两块 | O(√n) |
| 删除 erase(k) | 定位后块内 splice 删除；若相邻块都偏小可合并 | O(√n) |
| get(k) | 定位后返回块内元素 | O(√n) |
const S = 3; // 块容量上限，实际按 ⌈√n⌉ 取值
function locate(k: number): [number, number] {
let acc = 0;
for (let bi = 0; bi < blocks.length; bi++) {
if (acc + blocks[bi].length >= k) return [bi, k - acc];
acc += blocks[bi].length;
}
return [blocks.length - 1, blocks[blocks.length - 1].length];
}
function insert(k: number, v: number) {
const [bi, off] = locate(k);
blocks[bi].splice(off, 0, v);
if (blocks[bi].length > S) {
const mid = Math.ceil(blocks[bi].length / 2);
const right = blocks[bi].splice(mid); // 后半部分
blocks.splice(bi + 1, 0, right); // 分裂成两块
}
}