algorithm - 插入/删除/排名/选择查询的最佳数据结构/算法

Question

到目前为止，我知道像 AVL 树和红黑树这样的自平衡 BST 可以在 O(log n) 次内完成这些操作。

但是，要使用这些结构，我们必须自己实现AVL树或RB树。

我听说有一种算法/实现这四个操作而不使用自平衡 BST。

我们自己定义的结构，需要写那么多行。但是，我听说有可能在不到 100 行代码中支持这四个运算符:\

你们有什么想法应该怎么做吗？

除了BST，还有其他可能的选择吗？

Answer 1

如评论中所述，如果您想维护一组整数并且可以将坐标压缩作为预处理步骤(例如，因为您的算法是离线的并且知道所有 future 的查询)，您可以使用 binary-indexed tree 来支持每次操作在 O(log n) 中插入/删除/排名/选择数字。这是 C++ 中的示例:

int tree[N];  // where N is the number of compressed coordinates
const int maxl = floor(log(N)/log(2));

void insert(int i) { // 1 <= i <= N
  for (; i <= N; i += i & -i) ++tree[i];
}

void remove(int i) { // 1 <= i <= N
  for (; i <= N; i += i & -i) --tree[i];
}

int rank(int i) { // 1 <= i <= N
  int sum = 0;
  for (; i; i -= i & -i) sum += tree[i];
  return sum;
}

int select(int k) { // k is 1-based
  int ans = 0, s = 0;
  for (int i = maxl; i >= 0; --i) // maxl = largest i s.t. (1<<i) <= N
    if (s + tree[ans + (1<<i)] < k) {
      ans += 1<<i;
      s += tree[ans];
    }
  return ans+1;
}

select函数有点神奇。它重用更高位的结果来计算 O(1) 中的 ans + (1<<i) 的前缀和，恕我直言，这非常酷 :) 这样它只需要时间 O(log n)，而不是 O(log^2 n)使用标准的二进制搜索很容易实现。