用块状链表实现平衡树

· · 算法·理论

引入

在 OI 里面我们经常会遇到一些需要用到平衡树的题。虽然其中大部分题都可以用 std::set 解决，但是总有那么一些东西是 std::set 解决不了的，比如查排名之类的。

那么这个时候，我们要么用 pbds 里面的 tree 要么自己写平衡树。但 pbds 里面的平衡树用起来非常麻烦，要记一堆什么乱七八糟的玩意，还不好调。那么我们最好的方案便是自己写一个平衡树。

但平衡树的码量是众所周知的大，动不动就上百行，而且一般都是写半小时调两小时，写完平衡树考试都结束了。再加上大部分平衡树维护平衡的方式都非常难记，各种左右乱转和分类讨论完全写不了。

上回书说到，我们用字典树实现了平衡树。虽然它跑的快、代码短、功能多，但是空间占用多一个 \log w 使得其无法通过加强版平衡树模板 并且只能维护极其有限的一些类型的数据，我们需要一些更好的方法。

那么我们直接给出更好理解的方法：使用块状链表来写平衡树。

中心思想

我们将需要维护的有序数列划分成 l 段，平均每段有 m 个元素。

由于数列的有序性，你在查找的时候可以整块整块地跳，找到目标块之后再在该块内进行查找，总体时间复杂度是 O(l+m)。插入时只会使得一个块内的元素被移动，为 O(l+m)。

根据均值不等式，l,m\ge 0\implies l+m\ge 2\sqrt{l\cdot m}=2\sqrt{n}，当且仅当 l=m=\sqrt n 时等号成立。此时我们发现，时间复杂度来到了 O(\sqrt n)。

当然，为了保证 l,m\approx\sqrt n，你需要动态记录块长度，若某个块长度过大，则把它分裂成两个小块；如果某个块过小，则尝试把它接到旁边一个块上。

具体实现上，你可以用 std::vector 套 std::vector，使得外层块查找也可以二分，时间复杂度虽然没变，但是常数会小很多。

具体实现

平衡树的基本操作无非就是这 6 个：

我们一个一个拆解它们。

辅助操作：块分裂

用于维护块长不过大。一般来说，我们控制分裂阈值为 2\sqrt n。

void split(BlockList::iterator block) {
    // 检查并分裂 block 所指向的块。
    if (block->size() > BlockSize << 1) {
        // 此块大小达到了分裂阈值。
        block = std::prev(blockList.emplace(std::next(block), std::make_move_iterator(block->begin() + BlockSize), std::make_move_iterator(block->end())));
        // 将此块的后半部分移动到一个新块上，并将这个新块插入到这个块的后面，更新此块的迭代器位置。
        // 这种使用 emplace 以及 make_move_iterator 的实现方法使用了原位构造以及移动迭代器，常数会小很多。
        block->resize(BlockSize);
        // 更新此块大小。
    }
}

辅助操作：块合并

用于维护块长不过小。一般来说，如果两个块合并起来的大小也没有超过 2\sqrt n，我们就把它们并起来。

void merge(BlockList::iterator block) {
    // 检查并合并 block 所指向的块以及其后面一个块。
    if (std::next(block) != blockList.end() && block->size() + std::next(block)->size() < BlockSize << 1) {
        // 两块大小之和达到了合并要求。
        block->insert(block->end(), std::make_move_iterator(std::next(block)->begin()), std::make_move_iterator(std::next(block)->end()));
        // 将后面一个块并到这个块的最后。
        blockList.erase(std::next(block));
        // 后面的块此时已经空了，可以直接抹掉。
    }
}

插入

先找到待插入值所应当在的块，然后在这个块内查询待插入值所应当在的位置，然后插入它，最后检查分裂。

void insert(const Value& value) {
    // 插入 value。
    auto block = std::upper_bound(blockList.begin(), blockList.end(), value, [](const Value& value, const Block& block) -> bool { return block.back() >= value; });
    // 二分查找第一个满足 block.back() >= value 的块（value 所应当在的块），若没有则为 blockList.end()。
    if (block == blockList.end()) {
        // 不存在这样的块，说明 value 比现有的所有元素都大，应当插入到最后面。
        if (blockList.empty()) {
            // 特判数列为空的情况，此时需要单开一个块。
            blockList.emplace_back(1, value);
        } else {
            blockList.back().push_back(value);
            // 将其插入到最后一个块的后面。
            split(std::prev(blockList.end()));
            // 检查分裂最后一个块。
        }
    } else {
        block->insert(std::lower_bound(block->begin(), block->end(), value), value);
        // 二分查找 value 应当插入到的位置，然后插入它。
        split(block);
        // 检查分裂这个块。
    }
}

删除

先找到待删除值所应当在的块，然后在这个块内查询待删除值所应当在的位置，然后删除它，最后检查合并。

void erase(const Value& value) {
    // 删除 value。
    auto block = std::upper_bound(blockList.begin(), blockList.end(), value, [](const Value& value, const Block& block) -> bool { return block.back() >= value; });
    // 二分查找第一个满足 block.back() >= value 的块（value 所应当在的块），若没有则为 blockList.end()。
    block->erase(std::lower_bound(block->begin(), block->end(), value));
    // 在此块内二分查找并删除 value。
    if (block->empty())
        // 特判此块被删空的情况，此时需要直接抹掉这个块。
        blockList.erase(block);
    else
        merge(block);
        // 检查合并这个块。
}

由值查排名

先找到待查询值所应当在的块，然后累加这个块之前所有块的大小（因为这些块的元素显然都比待查询值小），然后在这个块内统计比待查询元素小的元素个数，加上去即可。

std::size_t queryRank(const Value& value) {
    // 由值查排名。
    auto block = std::upper_bound(blockList.begin(), blockList.end(), value, [](const Value& value, const Block& block) -> bool { return block.back() >= value; });
    // 二分查找第一个满足 block.back() >= value 的块（value 所应当在的块），若没有则为 blockList.end()。
    return std::accumulate(blockList.begin(), block, std::size_t(0), [](std::size_t sum, const Block& block) -> std::size_t { return sum + block.size(); })
           // 累加这个块之前所有块的大小。
        +  (block == blockList.end() ?
                // 不存在这样的块，说明 value 比现有的所有元素都大，比它小的元素都已经被统计完了。
                0 
            :
                std::lower_bound(block->begin(), block->end(), value) - block->begin());
                // 在此块内二分查找比 value 小的元素个数。
}

由排名查值

一个一个跳块，直到跳过的所有块的大小之和大于所查询的排名为止，然后取最后一个块的相应元素。

const Value& queryValue(std::size_t rank) {
    // 由排名查值。
    auto block = std::find_if(blockList.begin(), blockList.end(), [&rank](const Block& block) -> bool {
        if (block.size() > rank)
            // 此块包含该排名。
            return true;
        rank -= block.size();
        // 累加排名的一种方法。
        return false;
    });
    // 查询该排名所在的块。
    return block->at(rank);
}

查前驱

先找到待查询值所应当在的块，然后在这个块内找它的前驱即可。如果这个块的开头都不是它的前驱，说明它的前驱是前一个块的最后一个元素。

const Value& queryPrecursor(const Value& value) {
    // 查前驱。
    auto block = std::upper_bound(blockList.begin(), blockList.end(), value, [](const Value& value, const Block& block) -> bool { return block.back() >= value; });
    // 二分查找第一个满足 block.back() >= value 的块（value 所应当在的块），若没有则为 blockList.end()。
    return block == blockList.end() || block->front() >= value ?
               // 这个块的开头不是它的前驱或这个块不存在。
               std::prev(block)->back()
            :
               // 在这个块内查询 value 的前驱。
               *std::prev(std::lower_bound(block->begin(), block->end(), value));
}

查后继

先找到待查询值最后一次出现的块，然后在这个块内找它的后继即可。

const Value& querySuccessor(const Value& value) {
    // 查后继。
    auto block = std::upper_bound(blockList.begin(), blockList.end(), value, [](const Value& value, const Block& block) -> bool { return block.back() > value; });
    // 二分查找第一个满足 block.back() > value 的块（value 最后一次出现的块）。
    return *std::upper_bound(block->begin(), block->end(), value);
}

以上，平衡树六大基本操作全部实现。

至此，一锤定音。
尘埃，已然落定。

完整版代码非常简短，不含主函数只有 40 行。

using Value = std::int32_t;
using Block = std::vector<Value>;
using BlockList = std::vector<Block>;

constexpr std::size_t BlockSize = 512;

BlockList blockList;

inline void split(BlockList::iterator block) noexcept { block->size() > BlockSize << 1 && (block = std::prev(blockList.emplace(std::next(block), std::make_move_iterator(block->begin() + BlockSize), std::make_move_iterator(block->end()))), block->resize(BlockSize), true); }
inline void merge(BlockList::iterator block) noexcept { std::next(block) != blockList.end() && block->size() + std::next(block)->size() < BlockSize << 1 && (block->insert(block->end(), std::make_move_iterator(std::next(block)->begin()), std::make_move_iterator(std::next(block)->end())), blockList.erase(std::next(block)), true); }

void insert(const Value& value) noexcept {
    auto block = std::upper_bound(blockList.begin(), blockList.end(), value, [](const Value& value, const Block& block) -> bool { return block.back() >= value; });
    block == blockList.end() ? (blockList.empty() ? void(blockList.emplace_back(1, value)) : (blockList.back().push_back(value), split(std::prev(blockList.end())))) : (block->insert(std::lower_bound(block->begin(), block->end(), value), value), split(block));
}

void erase(const Value& value) noexcept {
    auto block = std::upper_bound(blockList.begin(), blockList.end(), value, [](const Value& value, const Block& block) -> bool { return block.back() >= value; });
    block->erase(std::lower_bound(block->begin(), block->end(), value)), block->empty() ? void(blockList.erase(block)) : merge(block);
}

std::size_t queryRank(const Value& value) noexcept {
    auto block = std::upper_bound(blockList.begin(), blockList.end(), value, [](const Value& value, const Block& block) -> bool { return block.back() >= value; });
    return std::accumulate(blockList.begin(), block, std::size_t(0), [](std::size_t sum, const Block& block) -> std::size_t { return sum + block.size(); }) + (block == blockList.end() ? 0 : std::lower_bound(block->begin(), block->end(), value) - block->begin());
}

const Value& queryValue(std::size_t rank) noexcept {
    auto block = std::find_if(blockList.begin(), blockList.end(), [&rank](const Block& block) -> bool { if (block.size() > rank) return true; rank -= block.size(); return false; });
    return block->at(rank);
}

const Value& queryPrecursor(const Value& value) noexcept {
    auto block = std::upper_bound(blockList.begin(), blockList.end(), value, [](const Value& value, const Block& block) -> bool { return block.back() >= value; });
    return block == blockList.end() || block->front() >= value ? std::prev(block)->back() : *std::prev(std::lower_bound(block->begin(), block->end(), value));
}

const Value& querySuccessor(const Value& value) noexcept {
    auto block = std::upper_bound(blockList.begin(), blockList.end(), value, [](const Value& value, const Block& block) -> bool { return block.back() > value; });
    return *std::upper_bound(block->begin(), block->end(), value);
}

优劣势分析

总体来说，用块状链表实现的平衡树优点大于缺点。

优势

劣势