BinaryTrie
(data-structure/binarytrie.hpp)

• View this file on GitHub
• Last update: 2023-03-13 21:53:46+09:00
• Include: #include "data-structure/binarytrie.hpp"

説明

挿入する値はすべて非負整数である必要がある

• BinaryTrie<T,D>(): Constructor。$2^{\mathrm{D}}$未満の値を入れられる

• insert(val, xor_val): valを1つ追加。$O(\mathrm{D})$

• erase(val, xor_val): valを1つ削除。$O(\mathrm{D})$

• add(val, num, xor_val): valをnum個追加。$O(\mathrm{D})$

• min(xor_val): 最小値を取得。$O(\mathrm{D})$

• max(xor_val): 最大値を取得。$O(\mathrm{D})$

• kth_elem(k, xor_val): $k$番目の値を取得。$O(\mathrm{D})$

• lower_bound(val, xor_val): val以上の値の最小値を取得。$O(\mathrm{D})$

• upper_bound(val, xor_val): valを超える値の最小値を取得。$O(\mathrm{D})$

• order(val, xor_val): valが小さい方から何番目かを取得。$O(\mathrm{D})$

• count(val): valの個数を取得。$O(\mathrm{D})$

• size(): 値の種類数を取得。$O(1)$

• num_size(): 入れられた値の個数を取得。$O(1)$

• reserve(s): $s$個の領域を確保しておく。$O(s)$

• xor_all(x): xorの値を更新。$O(1)$

• clear(): 要素をすべて削除する

Verified with

• test/yosupo/Data-Structure/Set-Xor-Min.test.cpp

Code

template <class T, size_t MAX_DIGIT>
struct BinaryTrie {
  struct Node {
    int cnt = 0;
    int ch[2] = { -1, -1 };
  };
  T lazy = 0;
  BinaryTrie() : root(1){}
  void xor_all(T x){ lazy ^= x; }
  void reserve(int s){ root.reserve(s); }
  void insert(T val, T xor_val = 0){ add(val, 1, xor_val); }
  void erase(T val, T xor_val = 0){ add(val, -1, xor_val); }
  void add(T val, int num, T xor_val = 0){
    const T nval = val ^ lazy ^ xor_val;
    int idx = 0;
    root[idx].cnt += num;
    for(int i = MAX_DIGIT-1; i >= 0; i--){
      const int f = nval >> i & 1;
      if(root[idx].ch[f] == -1){
        root[idx].ch[f] = (int)root.size();
        root.emplace_back(Node());
      }
      idx = root[idx].ch[f];
      root[idx].cnt += num;
    }
  }
  void clear(){
    root = { 0 };
    lazy = 0;
  }
  T min(T xor_val = 0) const{ return kth_elem(0, xor_val); }
  T max(T xor_val = 0) const{ return kth_elem(num_size()-1, xor_val); }
  T kth_elem(int k, T xor_val = 0) const{
    xor_val ^= lazy;
    int idx = 0;
    T res = 0;
    for(int i = MAX_DIGIT-1; i >= 0; i--){
      const int f = xor_val >> i & 1;
      const int l = root[idx].ch[f];
      const int r = root[idx].ch[!f];
      if(l == -1 || root[l].cnt <= k){
        if(l != -1) k -= root[l].cnt;
        idx = r;
        res |= T(1) << i;
      }else idx = l;
    }
    return res;
  }
  T lower_bound(T val, T xor_val = 0) const{
    return kth_elem(order(val, xor_val));
  }
  T upper_bound(T val, T xor_val = 0) const{
    return kth_elem(order(val+1, xor_val));
  }
  int order(T val, T xor_val = 0) const{
    xor_val ^= lazy;
    int idx = 0, ord = 0;
    for(int i = MAX_DIGIT-1; i >= 0; i--){
      const int f = xor_val >> i & 1;
      const int l = root[idx].ch[f];
      const int r = root[idx].ch[!f];
      if(val >> i & 1){
        if(l != -1) ord += root[l].cnt;
        idx = r;
      }else idx = l;
      if(idx == -1) break;
    }
    return ord;
  }
  int count(T val) const{
    const int t = find(val);
    return t == -1 ? 0 : root[t].cnt;
  }
  int size() const{ return root.size(); }
  int num_size() const{ return root[0].cnt; }
  private:
  vector<Node> root;
  int find(T val, T xor_val = 0) const{
    const T nval = val ^ lazy ^ xor_val;
    int idx = 0;
    for(int i = MAX_DIGIT-1; i >= 0; i--){
      const int f = nval >> i & 1;
      if(root[idx].ch[f] == -1) return -1;
      idx = root[idx].ch[f];
    }
    return idx;
  }
};

#line 1 "data-structure/binarytrie.hpp"
template <class T, size_t MAX_DIGIT>
struct BinaryTrie {
  struct Node {
    int cnt = 0;
    int ch[2] = { -1, -1 };
  };
  T lazy = 0;
  BinaryTrie() : root(1){}
  void xor_all(T x){ lazy ^= x; }
  void reserve(int s){ root.reserve(s); }
  void insert(T val, T xor_val = 0){ add(val, 1, xor_val); }
  void erase(T val, T xor_val = 0){ add(val, -1, xor_val); }
  void add(T val, int num, T xor_val = 0){
    const T nval = val ^ lazy ^ xor_val;
    int idx = 0;
    root[idx].cnt += num;
    for(int i = MAX_DIGIT-1; i >= 0; i--){
      const int f = nval >> i & 1;
      if(root[idx].ch[f] == -1){
        root[idx].ch[f] = (int)root.size();
        root.emplace_back(Node());
      }
      idx = root[idx].ch[f];
      root[idx].cnt += num;
    }
  }
  void clear(){
    root = { 0 };
    lazy = 0;
  }
  T min(T xor_val = 0) const{ return kth_elem(0, xor_val); }
  T max(T xor_val = 0) const{ return kth_elem(num_size()-1, xor_val); }
  T kth_elem(int k, T xor_val = 0) const{
    xor_val ^= lazy;
    int idx = 0;
    T res = 0;
    for(int i = MAX_DIGIT-1; i >= 0; i--){
      const int f = xor_val >> i & 1;
      const int l = root[idx].ch[f];
      const int r = root[idx].ch[!f];
      if(l == -1 || root[l].cnt <= k){
        if(l != -1) k -= root[l].cnt;
        idx = r;
        res |= T(1) << i;
      }else idx = l;
    }
    return res;
  }
  T lower_bound(T val, T xor_val = 0) const{
    return kth_elem(order(val, xor_val));
  }
  T upper_bound(T val, T xor_val = 0) const{
    return kth_elem(order(val+1, xor_val));
  }
  int order(T val, T xor_val = 0) const{
    xor_val ^= lazy;
    int idx = 0, ord = 0;
    for(int i = MAX_DIGIT-1; i >= 0; i--){
      const int f = xor_val >> i & 1;
      const int l = root[idx].ch[f];
      const int r = root[idx].ch[!f];
      if(val >> i & 1){
        if(l != -1) ord += root[l].cnt;
        idx = r;
      }else idx = l;
      if(idx == -1) break;
    }
    return ord;
  }
  int count(T val) const{
    const int t = find(val);
    return t == -1 ? 0 : root[t].cnt;
  }
  int size() const{ return root.size(); }
  int num_size() const{ return root[0].cnt; }
  private:
  vector<Node> root;
  int find(T val, T xor_val = 0) const{
    const T nval = val ^ lazy ^ xor_val;
    int idx = 0;
    for(int i = MAX_DIGIT-1; i >= 0; i--){
      const int f = nval >> i & 1;
      if(root[idx].ch[f] == -1) return -1;
      idx = root[idx].ch[f];
    }
    return idx;
  }
};

Back to top page