Geek asks and answers

Better data structure / Algorithm for insert / delete / rank / select queries

So far, I know that a self-balancing BST, such as the AVL tree and the Red Black Tree, can perform these operations O (log n) times.

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

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

With our own specific structure, we need to write so many lines. However, I heard that it is possible to support these four statements in less than 100 line code: \

Do you have any ideas on how to do this?

Besides BST, are there any other options?

+3
source share
1 answer

, , (, ), /// O (log n) . ++:

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 . ans + (1<<i) O (1), :) , O (log n) O (log n), O (log ^ 2 n), .

+3

More articles:


All Articles