到目前为止，我知道，自我平衡的BST像AVL树和红黑树可以在O（log n）的时间执行这些操作。

So far, I know that self-balancing BST like AVL tree and Red Black Tree can do these operations in O(log n) times.

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

However, to use these structures, we must implement AVL tree or RB tree ourselves.

我听说有一个算法/实现这四个操作，而无需使用自动平衡BST。

I have heard that there is an algorithm/ implementation of these four operations without using self-balancing BST.

用我们自己定义的结构，我们需要写那么多行。不过，我听说有在不到100线$​​ C $ C支持这四大运营商的可能性：\

With our own defined structure, we need to write so many lines. However, I have heard that there is a possibility of supporting these four operators in less than 100 lines code :\

难道你们对这个应该怎么做任何想法？

Do you guys have any ideas on how this should be done?

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

Other than BST, is there any other possible options?

推荐答案

正如在评论中，如果你想保持一个整数集，你可以做一个坐标COM pression为preprocessing一步（例如，因为你的算法处于脱机状态，知道所有的将来查询），你可以使用的二进制索引树支持插入/删除/等级/选择数为O（log n）的每个操作。下面是在C ++中的一个例子：

As mentioned in the comments, if you want to maintain a set of integers and you can do a coordinate compression as a preprocessing step (e.g. because your algorithm is offline and knows all the future queries), you can use a binary-indexed tree to support insert/delete/rank/select of numbers in O(log n) per operation. Here's an example in 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;
}

在选择函数有点不可思议。它重用来自较高位的结果来计算答+的preFIX款项（1 LT;＆LT;我）在O（1），这是pretty的酷恕我直言:)这种方式只需要，而不是O时间O（log n）的，（对数2 ^ n）的，很容易达到使用标准的二进制搜索。

The select function is somewhat magical. It reuses the results from higher bits to compute the prefix sum of ans + (1<<i) in O(1), which is pretty cool IMHO :) This way it only takes time O(log n), instead of the O(log^2 n) that is easy to achieve using a standard binary search.