Binary Trie

Binary trie

Decompose numbers into binary string and perform trie operations.

The code below supports:

• Insert/Delete operation.
• Get the k-th numbers in the trie.

Code

const int mod = 65536;
const int N = 250015;
struct trie {
  trie *bit[2];
  int cnt;
  trie() {
    bit[0] = bit[1] = NULL;
    cnt = 0;
  }
};

trie *root = new trie();
long long seed, mul, add, n, k, a[N];

void trieinsert(long long x) {
  trie *p = root;
  for (int i = 30; i >= 0; --i) {
    int nxt = (x >> i) & 1ll;
    if (p -> bit[nxt] == NULL)
      p -> bit[nxt] = new trie();
    ++(p -> cnt);
    p = p -> bit[nxt];
  }
  ++(p -> cnt);
}

void triedel(long long x) {
  trie *p = root;
  for (int i = 30; i >= 0; --i) {
    int nxt = (x >> i) & 1ll;
    --(p -> bit[nxt] -> cnt);
    if (p -> bit[nxt] -> cnt == 0) {
      p -> bit[nxt] = NULL;
      return;
    } else
      p = p -> bit[nxt];
  }
}

long long get(int kth) {
  long long res = 0;
  trie *p = root;
  for (int i = 30; i >= 0; --i)
    if (p -> bit[0] != NULL && p -> bit[0] -> cnt >= kth) {
      res = res << 1ll;
      p = p -> bit[0];
    } else if (p -> bit[1] != NULL) {
      if (p -> bit[0] != NULL)
        kth -= p -> bit[0] -> cnt;
      res = res << 1ll | 1ll;
      p = p -> bit[1];
    }
  return res;
}