是否存在支持O(logn)插入、删除及带距离查找的有序数据结构？

嘿，这两个问题本质上指向同一个完美解决方案——有序统计树（Order Statistic Tree, OST），正好能覆盖你所有的需求！

问题1：是否存在支持O(logn)插入、删除及带距离查找的有序结构？ #

当然存在！有序统计树就是专门为这类场景设计的：

• 它是平衡二叉搜索树（比如红黑树）的变种，每个节点额外维护了其所在子树的节点总数
• 核心操作的时间复杂度全部为O(logn)：
  • 插入/删除：和普通平衡BST一致，同时只需在操作路径上更新子树大小，额外开销可以忽略
  • 带距离的查找：包含两种核心场景：
    1. 查找某个元素的排名（即小于该元素的元素数量，对应你说的“距离/索引”）
    2. 查找第k小的元素（按排名直接访问元素）
       这两个操作都能通过节点的子树大小信息，在遍历树时快速定位，全程O(logn)时间。

问题2：如何在支持O(logn)插入/删除的同时，快速统计小于某个值的元素数量？ #

你提到的std::multiset的痛点（std::distance是O(n)）确实是个问题，但有序统计树正好解决了这个问题。在C++里，GCC的__gnu_pbds扩展库就提供了现成的order_statistics_tree实现，完全匹配你的需求：

核心特性匹配： #

• 插入/删除：O(logn)时间，和std::multiset效率一致
• 统计小于某个值的元素数量：调用order_of_key(x)方法，直接返回小于x的元素个数，O(logn)时间，完美替代你之前用std::upper_bound统计的逻辑
• 按排名访问元素：调用find_by_order(k)方法，返回第k小元素的迭代器（索引从0开始），也是O(logn)时间

简单代码示例 #

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

// 基础版本：不支持重复元素（重复插入会被忽略）
template<typename T>
using OrderedStatTree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// 支持重复元素的版本：用pair<T, int>作为键，第二个int用来区分重复元素
// template<typename T>
// using OrderedStatTree = tree<pair<T, int>, null_type, less<pair<T, int>>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    OrderedStatTree<int> ost;

    // 插入元素
    ost.insert(3);
    ost.insert(1);
    ost.insert(4);
    ost.insert(1); // 基础版本会忽略这个重复插入，要支持的话用pair版本

    // 统计小于5的元素数量：输出4
    std::cout << "Elements less than 5: " << ost.order_of_key(5) << "\n";

    // 统计小于2的元素数量：输出2（两个1）
    std::cout << "Elements less than 2: " << ost.order_of_key(2) << "\n";

    // 获取第2小的元素（0索引）：输出3
    auto it = ost.find_by_order(2);
    std::cout << "3rd element (0-indexed): " << *it << "\n";

    // 删除一个1
    ost.erase(ost.find(1));
    std::cout << "After deleting one 1, elements less than 2: " << ost.order_of_key(2) << "\n";

    return 0;
}

其他可选方案 #

如果你无法使用GCC的扩展库，也可以自行实现一个带子树大小维护的平衡BST（比如红黑树或AVL树）：

• 每个节点新增size字段，记录子树节点总数
• 插入/删除时，沿着操作路径更新所有祖先节点的size值
• 查找排名时，通过左子树的size判断当前节点的排名，进而决定遍历方向

另外，如果你的元素范围是已知且有限的，也可以用二叉索引树（Fenwick Tree）或线段树配合离散化实现，但这种方式在元素动态插入且范围不确定时，需要频繁调整离散化映射，灵活性不如有序统计树。

内容的提问来源于stack exchange，提问作者CCD