块状链表：用分块维护动态序列｜算法讲义

问题#

维护一个经常在任意位置插入、删除和访问的长序列。

连续数组支持 $O(1)$ 随机访问，但中间插入或删除需要移动 $O(n)$ 个元素。
普通链表能 $O(1)$ 修改已知节点，却需要 $O(n)$ 时间定位第 $k$ 个元素，并且每个元素都带指针，缓存局部性较差。

块状链表（Unrolled Linked List）让每个链表节点保存一小段连续数组。定位时按块跳过，进入目标块后再在块内移动元素。

核心思想#

设目标块长为 $B$ ：

链表节点内部用连续数组保存至多约 $2B$ 个元素。
插入使某块过大时，把它从中间裂成两块。
删除使相邻块过小时，把它们合成一块。
定位位置 $p$ 时，逐块减去块长，直到 $p$ 落入某块。

若各块大小保持在 $\Theta(B)$ ，块数约为 $n/B$ 。一次定位加块内搬移的复杂度为：

O\left(\frac nB+B\right).

取 $B\approx\sqrt n$ ，得到约 $O(\sqrt n)$ 。

不变量#

除空序列外，每个块都非空。
每个块大小不超过 $2B$ ；超过时立即裂块。
删除后若相邻两块合计不超过 $2B$ ，就合并它们，避免产生大量小块。
所有块的元素数之和始终等于序列总长度。

这些规则不要求每个块恰好为 $B$ ，只需让块数与块内长度都保持在合理范围。

复杂度#

在块大小保持平衡、 $B\approx\sqrt n$ 时：

按位置访问： $O(n/B)$ ，约 $O(\sqrt n)$
插入、删除：定位 $O(n/B)$ + 块内移动/重平衡 $O(B)$
顺序遍历： $O(n)$
空间： $O(n)$

这里的复杂度依赖重平衡不变量。如果从不并块，删除后可能留下大量小块并退化。

可独立编译的 C++17 模板#

下面是内存版动态整数序列。命令：

insert pos value：在位置 pos 前插入；
erase pos：删除位置 pos；
get pos：查询位置 pos；
print：输出整个序列。

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <list>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

class UnrolledList {
private:
    using Block = std::vector<long long>;
    using Iterator = std::list<Block>::iterator;
    using ConstIterator = std::list<Block>::const_iterator;

public:
    explicit UnrolledList(
        const std::vector<long long>& values,
        std::size_t target_block_size
    )
        : size_(0),
          target_block_size_(
              std::max<std::size_t>(1, target_block_size)
          ) {
        for (long long value : values) {
            push_back(value);
        }
    }

    std::size_t size() const {
        return size_;
    }

    long long at(std::size_t position) const {
        const auto [block, offset] = locate(position);
        return (*block)[offset];
    }

    void insert(std::size_t position, long long value) {
        if (position > size_) {
            throw std::out_of_range("insert position out of range");
        }

        if (blocks_.empty()) {
            blocks_.emplace_back();
        }

        auto [block, offset] = locate_for_insert(position);
        block->insert(
            block->begin() + static_cast<std::ptrdiff_t>(offset),
            value
        );
        ++size_;
        split_if_needed(block);
    }

    void erase(std::size_t position) {
        auto [block, offset] = locate(position);
        block->erase(
            block->begin() + static_cast<std::ptrdiff_t>(offset)
        );
        --size_;
        rebalance_after_erase(block);
    }

    std::vector<long long> to_vector() const {
        std::vector<long long> result;
        result.reserve(size_);
        for (const Block& block : blocks_) {
            result.insert(result.end(), block.begin(), block.end());
        }
        return result;
    }

private:
    std::list<Block> blocks_;
    std::size_t size_;
    std::size_t target_block_size_;

    void push_back(long long value) {
        if (blocks_.empty()) {
            blocks_.emplace_back();
        }
        blocks_.back().push_back(value);
        ++size_;
        split_if_needed(std::prev(blocks_.end()));
    }

    std::pair<Iterator, std::size_t> locate_for_insert(
        std::size_t position
    ) {
        if (position == size_) {
            Iterator last = std::prev(blocks_.end());
            return {last, last->size()};
        }

        std::size_t skipped = 0;
        for (Iterator it = blocks_.begin(); it != blocks_.end(); ++it) {
            if (position < skipped + it->size()) {
                return {it, position - skipped};
            }
            skipped += it->size();
        }
        throw std::logic_error("broken block sizes");
    }

    std::pair<Iterator, std::size_t> locate(
        std::size_t position
    ) {
        if (position >= size_) {
            throw std::out_of_range("position out of range");
        }

        std::size_t skipped = 0;
        for (Iterator it = blocks_.begin(); it != blocks_.end(); ++it) {
            if (position < skipped + it->size()) {
                return {it, position - skipped};
            }
            skipped += it->size();
        }
        throw std::logic_error("broken block sizes");
    }

    std::pair<ConstIterator, std::size_t> locate(
        std::size_t position
    ) const {
        if (position >= size_) {
            throw std::out_of_range("position out of range");
        }

        std::size_t skipped = 0;
        for (
            ConstIterator it = blocks_.begin();
            it != blocks_.end();
            ++it
        ) {
            if (position < skipped + it->size()) {
                return {it, position - skipped};
            }
            skipped += it->size();
        }
        throw std::logic_error("broken block sizes");
    }

    void split_if_needed(Iterator block) {
        const std::size_t maximum_size =
            target_block_size_ * 2;
        if (block->size() <= maximum_size) {
            return;
        }

        const std::size_t middle = block->size() / 2;
        Block right(
            std::make_move_iterator(
                block->begin() + static_cast<std::ptrdiff_t>(middle)
            ),
            std::make_move_iterator(block->end())
        );
        block->erase(
            block->begin() + static_cast<std::ptrdiff_t>(middle),
            block->end()
        );
        blocks_.insert(std::next(block), std::move(right));
    }

    void rebalance_after_erase(Iterator block) {
        if (block->empty()) {
            Iterator next = blocks_.erase(block);
            if (blocks_.empty()) {
                return;
            }
            block = next == blocks_.end() ? std::prev(next) : next;
        }

        const std::size_t maximum_size =
            target_block_size_ * 2;
        Iterator next = std::next(block);
        if (
            next != blocks_.end() &&
            block->size() + next->size() <= maximum_size
        ) {
            block->insert(
                block->end(),
                std::make_move_iterator(next->begin()),
                std::make_move_iterator(next->end())
            );
            blocks_.erase(next);
            return;
        }

        if (block != blocks_.begin()) {
            Iterator previous = std::prev(block);
            if (
                previous->size() + block->size() <= maximum_size
            ) {
                previous->insert(
                    previous->end(),
                    std::make_move_iterator(block->begin()),
                    std::make_move_iterator(block->end())
                );
                blocks_.erase(block);
            }
        }
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int operation_count = 0;
    std::cin >> n >> operation_count;
    if (n < 0 || operation_count < 0) {
        return 0;
    }

    std::vector<long long> initial(static_cast<std::size_t>(n));
    for (long long& value : initial) {
        std::cin >> value;
    }

    const std::size_t expected_size =
        static_cast<std::size_t>(n + operation_count) + 1;
    const std::size_t block_size =
        static_cast<std::size_t>(
            std::sqrt(static_cast<double>(expected_size))
        ) + 1;
    UnrolledList sequence(initial, block_size);

    while (operation_count-- > 0) {
        std::string operation;
        std::cin >> operation;

        if (operation == "insert") {
            std::size_t position = 0;
            long long value = 0;
            std::cin >> position >> value;
            sequence.insert(position, value);
        } else if (operation == "erase") {
            std::size_t position = 0;
            std::cin >> position;
            sequence.erase(position);
        } else if (operation == "get") {
            std::size_t position = 0;
            std::cin >> position;
            std::cout << sequence.at(position) << '\n';
        } else if (operation == "print") {
            const std::vector<long long> values = sequence.to_vector();
            for (std::size_t i = 0; i < values.size(); ++i) {
                if (i != 0) {
                    std::cout << ' ';
                }
                std::cout << values[i];
            }
            std::cout << '\n';
        }
    }
}

示例#

输入：

4 7
10 20 30 40
get 2
insert 2 25
print
erase 0
get 3
insert 4 50
print

输出：

30
10 20 25 30 40
40
20 25 30 40 50

插入 25 只在目标块内移动元素；当块超过上限时，模板会自动把它从中间裂开。

易错点#

只裂不并：大量删除会留下很多小块，使定位退化到线性时间。
总长度不同步：每次插入、删除都必须恰好更新一次 size_。
边界位置含义不清：插入允许位置等于长度，访问和删除只允许位置小于长度。
保存 vector 内部引用：块内插入、删除可能让迭代器和引用失效，不要跨操作保存它们。
合并后继续使用被删块迭代器：链表擦除节点后，该节点迭代器失效。
把理论根号复杂度当作无条件保证：块长应结合预期数据规模选择，且必须维持块大小不变量。
外存版逐元素读写：磁盘访问应以整块为单位，否则会失去块状结构的意义。

边界测试#

空序列插入；删除到空后再次插入。
单元素的访问与删除。
在开头、中间、末尾插入。
删除每一块的首、尾元素。
连续插入触发多次裂块；连续删除触发空块删除与前后并块。
块边界位置的访问与修改。
随机操作序列，与 std::vector 的结果对拍，并在每步检查总长度。

变体#

泛型块状链表：把 long long 替换为模板类型；同时约束元素可移动。
有序块索引：每块维护最大键，先按块最大值定位，再在块内二分，适合动态有序集合。
聚合信息：每块维护和、最大值或频次，可增加根号级区间查询；修改后重建相关块。

问题#