Binary Trie
(data-structure/binary-trie.hpp)

• View this file on GitHub
• Last update: 2026-07-09 13:20:35+09:00
• Include: #include "data-structure/binary-trie.hpp"

非負整数の multiset を bit ごとの trie で管理するデータ構造．

BinaryTrie<I, B, C> として使う．I は値の型，B は見る bit 数，C は個数の型．管理できる値は $0 \leq x < 2^B$．

• add(x, cnt = 1)：値 x の個数を cnt 増やす．削除は cnt = -1 で行う．
• count(x)：値 x の個数を返す．
• contains(x)：値 x が存在するか判定する．
• insert(x)：値 x が存在しなければ追加して true を返す．既に存在する場合は何もせず false を返す．
• erase(x)：値 x が存在すれば 1 個削除して true を返す．存在しない場合は何もせず false を返す．
• count_leq(x, xor_val = 0)：(y xor xor_val) <= x を満たす要素 y の個数を返す．
• min_element(k = 0, xor_val = 0)：y xor xor_val が小さい順で k 番目の要素 y を返す．
• max_element(k = 0, xor_val = 0)：y xor xor_val が大きい順で k 番目の要素 y を返す．

min_element, max_element の k は 0-indexed．存在する要素数未満であることを要求する．

add(x, cnt) は x の個数が負にならないことを要求する．

各操作の計算量は $O(B)$．

Verified with

• verify/data-structure/LC_set_xor_min.test.cpp

Code

#pragma once

template <class I = int, int B = 30, class C = int>
struct BinaryTrie {
  struct Node {
    Node* next[2];
    C count;
    Node() : count(0) { next[0] = next[1] = nullptr; }
  };
  BinaryTrie() : root(new Node()) {}
  void add(I val, C cnt = 1) { add(root, val, cnt); }
  C count(I val) { return count(root, val); }
  bool contains(I val) { return count(val) > 0; }
  bool insert(I val) {
    if (contains(val)) return false;
    add(val);
    return true;
  }
  bool erase(I val) {
    if (!contains(val)) return false;
    add(val, -1);
    return true;
  }
  C count_leq(I val, I xor_val = 0) { return count_leq(root, val, xor_val); }
  // 0-indexed
  I min_element(C index = 0, I xor_val = 0) { return min_element(root, index, xor_val); }
  I max_element(C index = 0, I xor_val = 0) { return max_element(root, index, xor_val); }

 private:
  Node* root;
  Node* get_child(Node* node, int x) {
    if (!node->next[x]) node->next[x] = new Node();
    return node->next[x];
  }
  C count(Node* node) { return node ? node->count : 0; }
  void add(Node* node, I val, C cnt, int k = B - 1) {
    node->count += cnt;
    if (k >= 0) add(get_child(node, (val >> k) & 1), val, cnt, k - 1);
  }
  C count(Node* node, I val, int k = B - 1) {
    if (!node) return 0;
    if (k == -1) return node->count;
    return count(node->next[(val >> k) & 1], val, k - 1);
  }
  C count_leq(Node* node, I val, I xor_val, int k = B - 1) {
    if (!node) return 0;
    if (k == -1) return node->count;
    int t = (xor_val >> k) & 1;
    if ((val >> k) & 1)
      return count(node->next[t]) + count_leq(node->next[t ^ 1], val, xor_val, k - 1);
    else
      return count_leq(node->next[t], val, xor_val, k - 1);
  }
  I min_element(Node* node, C index, I xor_val, int k = B - 1) {
    assert(node);
    if (k == -1) return I{};
    int t = (xor_val >> k) & 1;
    C cnt0 = count(node->next[t]);
    if (index < cnt0) return min_element(node->next[t], index, xor_val, k - 1) | (I(t) << k);
    return min_element(node->next[t ^ 1], index - cnt0, xor_val, k - 1) | (I(t ^ 1) << k);
  }
  I max_element(Node* node, C index, I xor_val, int k = B - 1) {
    assert(node);
    if (k == -1) return I{};
    int t = (xor_val >> k) & 1;
    C cnt1 = count(node->next[t ^ 1]);
    if (index < cnt1) return max_element(node->next[t ^ 1], index, xor_val, k - 1) | (I(t ^ 1) << k);
    return max_element(node->next[t], index - cnt1, xor_val, k - 1) | (I(t) << k);
  }
};

/**
 * @brief Binary Trie
 * @docs docs/data-structure/binary-trie.md
 */

#line 2 "data-structure/binary-trie.hpp"

template <class I = int, int B = 30, class C = int>
struct BinaryTrie {
  struct Node {
    Node* next[2];
    C count;
    Node() : count(0) { next[0] = next[1] = nullptr; }
  };
  BinaryTrie() : root(new Node()) {}
  void add(I val, C cnt = 1) { add(root, val, cnt); }
  C count(I val) { return count(root, val); }
  bool contains(I val) { return count(val) > 0; }
  bool insert(I val) {
    if (contains(val)) return false;
    add(val);
    return true;
  }
  bool erase(I val) {
    if (!contains(val)) return false;
    add(val, -1);
    return true;
  }
  C count_leq(I val, I xor_val = 0) { return count_leq(root, val, xor_val); }
  // 0-indexed
  I min_element(C index = 0, I xor_val = 0) { return min_element(root, index, xor_val); }
  I max_element(C index = 0, I xor_val = 0) { return max_element(root, index, xor_val); }

 private:
  Node* root;
  Node* get_child(Node* node, int x) {
    if (!node->next[x]) node->next[x] = new Node();
    return node->next[x];
  }
  C count(Node* node) { return node ? node->count : 0; }
  void add(Node* node, I val, C cnt, int k = B - 1) {
    node->count += cnt;
    if (k >= 0) add(get_child(node, (val >> k) & 1), val, cnt, k - 1);
  }
  C count(Node* node, I val, int k = B - 1) {
    if (!node) return 0;
    if (k == -1) return node->count;
    return count(node->next[(val >> k) & 1], val, k - 1);
  }
  C count_leq(Node* node, I val, I xor_val, int k = B - 1) {
    if (!node) return 0;
    if (k == -1) return node->count;
    int t = (xor_val >> k) & 1;
    if ((val >> k) & 1)
      return count(node->next[t]) + count_leq(node->next[t ^ 1], val, xor_val, k - 1);
    else
      return count_leq(node->next[t], val, xor_val, k - 1);
  }
  I min_element(Node* node, C index, I xor_val, int k = B - 1) {
    assert(node);
    if (k == -1) return I{};
    int t = (xor_val >> k) & 1;
    C cnt0 = count(node->next[t]);
    if (index < cnt0) return min_element(node->next[t], index, xor_val, k - 1) | (I(t) << k);
    return min_element(node->next[t ^ 1], index - cnt0, xor_val, k - 1) | (I(t ^ 1) << k);
  }
  I max_element(Node* node, C index, I xor_val, int k = B - 1) {
    assert(node);
    if (k == -1) return I{};
    int t = (xor_val >> k) & 1;
    C cnt1 = count(node->next[t ^ 1]);
    if (index < cnt1) return max_element(node->next[t ^ 1], index, xor_val, k - 1) | (I(t ^ 1) << k);
    return max_element(node->next[t], index - cnt1, xor_val, k - 1) | (I(t) << k);
  }
};

/**
 * @brief Binary Trie
 * @docs docs/data-structure/binary-trie.md
 */

Back to top page