Binary Trie
(ds/binary_trie/binary_trie.hpp)

View this file on GitHub
Last update: 2026-07-12 04:39:25+09:00
Include: #include "ds/binary_trie/binary_trie.hpp"

Overview

BinaryTrie is a multiset of unsigned integers represented by their binary digits. It supports insertion, deletion, order statistics, and minimum or maximum xor queries in time proportional to the configured bit width.

Duplicate values are stored separately. xor_all(value) lazily applies xor to every value already in the trie.

Template Parameters

UInt: An unsigned integer type. Defaults to std::uint32_t.
BitWidth: The number of low bits used by the trie. Defaults to all bits of UInt. Every inserted value and xor operand must fit in these bits.

An exclusive upper bound may be larger than the largest representable BitWidth-bit value when that bound fits in UInt. For example, with BitWidth == 30, passing 1U << 30 includes every possible value.

Methods

Let $B$ be BitWidth.

Method	Description	Complexity
`BinaryTrie()`	Constructs an empty trie.	$O(1)$
`BinaryTrie(std::initializer_list<UInt> init)`	Constructs a trie containing `init`.	$O(NB)$
`BinaryTrie(Iterator first, Iterator last)`	Constructs a trie from a range.	$O(NB)$
`int size() const`	Returns the number of values, including duplicates.	$O(1)$
`bool empty() const`	Returns whether the trie is empty.	$O(1)$
`node_id root() const`	Returns the root node handle.	$O(1)$
`node_id find(UInt value) const`	Returns the leaf handle for `value`, or `null_node` if absent.	$O(B)$
`const Node& node(node_id id) const`	Returns a read-only view of a node.	$O(1)$
`size_t node_count() const`	Returns allocated nodes, including the root.	$O(1)$
`void reserve(size_t n)`	Reserves storage for approximately `n` nodes.	$O(K)$
`UInt xor_mask() const`	Returns the current lazy xor mask.	$O(1)$
`void clear()`	Removes every value and resets the lazy xor.	$O(1)$
`node_id insert(UInt value, int multiplicity = 1)`	Inserts copies of `value` and returns its leaf handle.	$O(B)$
`bool erase_one(UInt value)`, `bool erase(UInt value)`	Removes one copy and returns whether one existed.	$O(B)$
`int erase_all(UInt value)`	Removes every copy and returns the number removed.	$O(B)$
`int count(UInt value) const`	Returns the multiplicity of `value`.	$O(B)$
`bool contains(UInt value) const`	Returns whether `value` exists.	$O(B)$
`void xor_all(UInt value)`	Applies xor with `value` to every stored value.	$O(1)$
`UInt kth(int k) const`	Returns the 0-indexed `k`-th smallest stored value.	$O(B)$
`UInt min() const`, `UInt max() const`	Returns the smallest or largest value. Requires a nonempty trie.	$O(B)$
`UInt kth_xor(int k, UInt value) const`	Returns the 0-indexed `k`-th smallest result among `stored_value ^ value`.	$O(B)$
`UInt min_xor(UInt value) const`, `UInt max_xor(UInt value) const`	Returns the minimum or maximum result among `stored_value ^ value`. Requires a nonempty trie.	$O(B)$
`int order_of_key(UInt value) const`, `int count_less(UInt value) const`	Returns the number of stored values strictly less than `value`.	$O(B)$
`int count_less_equal(UInt value) const`	Returns the number of stored values less than or equal to `value`.	$O(B)$
`int count_greater(UInt value) const`	Returns the number of stored values strictly greater than `value`.	$O(B)$
`int count_greater_equal(UInt value) const`	Returns the number of stored values greater than or equal to `value`.	$O(B)$
`int count_xor_less(UInt value, UInt upper) const`	Counts stored values for which `(stored_value ^ value) < upper`.	$O(B)$
`int count_xor_less_equal(UInt value, UInt upper) const`	Counts stored values for which `(stored_value ^ value) <= upper`.	$O(B)$
`int count_xor_greater(UInt value, UInt lower) const`	Counts stored values for which `(stored_value ^ value) > lower`.	$O(B)$
`int count_xor_greater_equal(UInt value, UInt lower) const`	Counts stored values for which `(stored_value ^ value) >= lower`.	$O(B)$
`int count_xor_range(UInt value, UInt lower, UInt upper) const`	Counts stored values for which `lower <= (stored_value ^ value) < upper`.	$O(B)$
`std::vector<UInt> to_vector() const`	Returns all values in sorted order, including duplicates.	$O(NB)$

count_less_xor(value, upper) is a compatibility alias for count_xor_less(value, upper).

node_id is an integer handle and null_node is its invalid value. A Node exposes child[2] and count. Handles remain valid across insertions and erasures and can index user-owned metadata; clear() invalidates every old handle except the root. References returned by node() may be invalidated by insertion, reserve(), or clear().

The child links describe the physically stored bit paths. After xor_all, logical values differ by xor_mask(); find(value) accounts for this mask automatically.

Here $K$ is the allocated node count. Erasing does not reclaim nodes.

Example

#include "ds/binary_trie/binary_trie.hpp"

#include <cstdint>
#include <iostream>

int main() {
    m1une::ds::BinaryTrie<std::uint32_t, 20> trie;
    trie.insert(2);
    trie.insert(7);
    trie.insert(7);

    std::cout << trie.min_xor(5) << "\n";  // min(2 ^ 5, 7 ^ 5) = 2
    std::cout << trie.kth(1) << "\n";      // 7

    trie.xor_all(3);
    std::cout << trie.min() << "\n";       // min(2 ^ 3, 7 ^ 3) = 1
    std::cout << trie.count(4) << "\n";    // 2
}

Verified with

verify/ds/binary_trie/binary_trie.test.cpp

Code

#ifndef M1UNE_DS_BINARY_TRIE_HPP
#define M1UNE_DS_BINARY_TRIE_HPP 1

#include <cassert>
#include <cstdint>
#include <initializer_list>
#include <limits>
#include <type_traits>
#include <vector>

namespace m1une {
namespace ds {

template <typename UInt = std::uint32_t, int BitWidth = std::numeric_limits<UInt>::digits>
struct BinaryTrie {
    static_assert(std::is_integral_v<UInt>);
    static_assert(std::is_unsigned_v<UInt>);
    static_assert(!std::is_same_v<UInt, bool>);
    static_assert(0 < BitWidth);
    static_assert(BitWidth <= std::numeric_limits<UInt>::digits);

    using node_id = int;
    static constexpr node_id null_node = -1;

    struct Node {
        node_id child[2];
        int count;

        Node() : child{null_node, null_node}, count(0) {}
    };

   private:
    std::vector<Node> nodes;
    UInt lazy_xor;

    static constexpr int bit(UInt value, int position) {
        return int((value >> position) & UInt(1));
    }

    static constexpr UInt value_mask() {
        if constexpr (BitWidth == std::numeric_limits<UInt>::digits) {
            return std::numeric_limits<UInt>::max();
        } else {
            return (UInt(1) << BitWidth) - UInt(1);
        }
    }

    static constexpr bool valid_value(UInt value) {
        return (value & ~value_mask()) == UInt(0);
    }

    node_id new_node() {
        nodes.emplace_back();
        return int(nodes.size()) - 1;
    }

    int subtree_size(node_id node) const {
        return node == null_node ? 0 : nodes[node].count;
    }

    node_id find_node(UInt value) const {
        node_id node = 0;
        value ^= lazy_xor;
        for (int position = BitWidth - 1; position >= 0; --position) {
            node = nodes[node].child[bit(value, position)];
            if (node == null_node || nodes[node].count == 0) {
                return null_node;
            }
        }
        return node;
    }

   public:
    BinaryTrie() : nodes(1), lazy_xor(0) {}

    BinaryTrie(std::initializer_list<UInt> init) : BinaryTrie() {
        for (UInt value : init) insert(value);
    }

    template <typename Iterator>
    BinaryTrie(Iterator first, Iterator last) : BinaryTrie() {
        while (first != last) {
            insert(*first);
            ++first;
        }
    }

    int size() const {
        return nodes[0].count;
    }

    bool empty() const {
        return size() == 0;
    }

    node_id root() const {
        return 0;
    }

    const Node& node(node_id id) const {
        assert(0 <= id && std::size_t(id) < nodes.size());
        return nodes[id];
    }

    node_id find(UInt value) const {
        assert(valid_value(value));
        return find_node(value);
    }

    std::size_t node_count() const {
        return nodes.size();
    }

    void reserve(std::size_t node_capacity) {
        nodes.reserve(node_capacity);
    }

    UInt xor_mask() const {
        return lazy_xor;
    }

    void clear() {
        nodes.clear();
        nodes.emplace_back();
        lazy_xor = 0;
    }

    node_id insert(UInt value, int multiplicity = 1) {
        assert(valid_value(value));
        assert(multiplicity > 0);
        value ^= lazy_xor;
        node_id node = 0;
        nodes[node].count += multiplicity;
        for (int position = BitWidth - 1; position >= 0; --position) {
            const int direction = bit(value, position);
            if (nodes[node].child[direction] == null_node) {
                const node_id child = new_node();
                nodes[node].child[direction] = child;
            }
            node = nodes[node].child[direction];
            nodes[node].count += multiplicity;
        }
        return node;
    }

    int count(UInt value) const {
        assert(valid_value(value));
        const node_id node = find_node(value);
        return node == null_node ? 0 : nodes[node].count;
    }

    bool contains(UInt value) const {
        return count(value) > 0;
    }

    bool erase_one(UInt value) {
        assert(valid_value(value));
        if (!contains(value)) return false;
        value ^= lazy_xor;
        int node = 0;
        --nodes[node].count;
        for (int position = BitWidth - 1; position >= 0; --position) {
            node = nodes[node].child[bit(value, position)];
            --nodes[node].count;
        }
        return true;
    }

    bool erase(UInt value) {
        return erase_one(value);
    }

    int erase_all(UInt value) {
        assert(valid_value(value));
        const int multiplicity = count(value);
        if (multiplicity == 0) return 0;
        value ^= lazy_xor;
        int node = 0;
        nodes[node].count -= multiplicity;
        for (int position = BitWidth - 1; position >= 0; --position) {
            node = nodes[node].child[bit(value, position)];
            nodes[node].count -= multiplicity;
        }
        return multiplicity;
    }

    void xor_all(UInt value) {
        assert(valid_value(value));
        lazy_xor ^= value;
    }

    UInt kth_xor(int k, UInt value) const {
        assert(0 <= k && k < size());
        assert(valid_value(value));
        const UInt effective_xor = lazy_xor ^ value;
        UInt result = 0;
        int node = 0;
        for (int position = BitWidth - 1; position >= 0; --position) {
            const int preferred = bit(effective_xor, position);
            const int preferred_size = subtree_size(nodes[node].child[preferred]);
            if (k < preferred_size) {
                node = nodes[node].child[preferred];
            } else {
                k -= preferred_size;
                node = nodes[node].child[preferred ^ 1];
                result |= UInt(1) << position;
            }
        }
        return result;
    }

    UInt kth(int k) const {
        return kth_xor(k, 0);
    }

    UInt min() const {
        return kth(0);
    }

    UInt max() const {
        return kth(size() - 1);
    }

    UInt min_xor(UInt value) const {
        return kth_xor(0, value);
    }

    UInt max_xor(UInt value) const {
        return kth_xor(size() - 1, value);
    }

    int count_less_xor(UInt value, UInt upper) const {
        assert(valid_value(value));
        if (!valid_value(upper)) return size();
        const UInt effective_xor = lazy_xor ^ value;
        int result = 0;
        int node = 0;
        for (int position = BitWidth - 1; position >= 0 && node != -1; --position) {
            const int zero = bit(effective_xor, position);
            if (bit(upper, position) == 1) {
                result += subtree_size(nodes[node].child[zero]);
                node = nodes[node].child[zero ^ 1];
            } else {
                node = nodes[node].child[zero];
            }
        }
        return result;
    }

    int count_xor_less(UInt value, UInt upper) const {
        return count_less_xor(value, upper);
    }

    int count_xor_less_equal(UInt value, UInt upper) const {
        assert(valid_value(value));
        assert(valid_value(upper));
        if (upper == value_mask()) return size();
        return count_xor_less(value, upper + UInt(1));
    }

    int count_xor_greater(UInt value, UInt lower) const {
        assert(valid_value(value));
        assert(valid_value(lower));
        return size() - count_xor_less_equal(value, lower);
    }

    int count_xor_greater_equal(UInt value, UInt lower) const {
        assert(valid_value(value));
        assert(valid_value(lower));
        return size() - count_xor_less(value, lower);
    }

    int count_xor_range(UInt value, UInt lower, UInt upper) const {
        assert(valid_value(value));
        assert(valid_value(lower));
        assert(lower <= upper);
        return count_xor_less(value, upper) -
               count_xor_less(value, lower);
    }

    int order_of_key(UInt value) const {
        return count_less_xor(0, value);
    }

    int count_less(UInt value) const {
        return order_of_key(value);
    }

    int count_less_equal(UInt value) const {
        assert(valid_value(value));
        if (value == value_mask()) return size();
        return count_less(value + UInt(1));
    }

    int count_greater(UInt value) const {
        return size() - count_less_equal(value);
    }

    int count_greater_equal(UInt value) const {
        return size() - count_less(value);
    }

    std::vector<UInt> to_vector() const {
        std::vector<UInt> result;
        result.reserve(size());
        for (int k = 0; k < size(); ++k) {
            result.push_back(kth(k));
        }
        return result;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DS_BINARY_TRIE_HPP

#line 1 "ds/binary_trie/binary_trie.hpp"



#include <cassert>
#include <cstdint>
#include <initializer_list>
#include <limits>
#include <type_traits>
#include <vector>

namespace m1une {
namespace ds {

template <typename UInt = std::uint32_t, int BitWidth = std::numeric_limits<UInt>::digits>
struct BinaryTrie {
    static_assert(std::is_integral_v<UInt>);
    static_assert(std::is_unsigned_v<UInt>);
    static_assert(!std::is_same_v<UInt, bool>);
    static_assert(0 < BitWidth);
    static_assert(BitWidth <= std::numeric_limits<UInt>::digits);

    using node_id = int;
    static constexpr node_id null_node = -1;

    struct Node {
        node_id child[2];
        int count;

        Node() : child{null_node, null_node}, count(0) {}
    };

   private:
    std::vector<Node> nodes;
    UInt lazy_xor;

    static constexpr int bit(UInt value, int position) {
        return int((value >> position) & UInt(1));
    }

    static constexpr UInt value_mask() {
        if constexpr (BitWidth == std::numeric_limits<UInt>::digits) {
            return std::numeric_limits<UInt>::max();
        } else {
            return (UInt(1) << BitWidth) - UInt(1);
        }
    }

    static constexpr bool valid_value(UInt value) {
        return (value & ~value_mask()) == UInt(0);
    }

    node_id new_node() {
        nodes.emplace_back();
        return int(nodes.size()) - 1;
    }

    int subtree_size(node_id node) const {
        return node == null_node ? 0 : nodes[node].count;
    }

    node_id find_node(UInt value) const {
        node_id node = 0;
        value ^= lazy_xor;
        for (int position = BitWidth - 1; position >= 0; --position) {
            node = nodes[node].child[bit(value, position)];
            if (node == null_node || nodes[node].count == 0) {
                return null_node;
            }
        }
        return node;
    }

   public:
    BinaryTrie() : nodes(1), lazy_xor(0) {}

    BinaryTrie(std::initializer_list<UInt> init) : BinaryTrie() {
        for (UInt value : init) insert(value);
    }

    template <typename Iterator>
    BinaryTrie(Iterator first, Iterator last) : BinaryTrie() {
        while (first != last) {
            insert(*first);
            ++first;
        }
    }

    int size() const {
        return nodes[0].count;
    }

    bool empty() const {
        return size() == 0;
    }

    node_id root() const {
        return 0;
    }

    const Node& node(node_id id) const {
        assert(0 <= id && std::size_t(id) < nodes.size());
        return nodes[id];
    }

    node_id find(UInt value) const {
        assert(valid_value(value));
        return find_node(value);
    }

    std::size_t node_count() const {
        return nodes.size();
    }

    void reserve(std::size_t node_capacity) {
        nodes.reserve(node_capacity);
    }

    UInt xor_mask() const {
        return lazy_xor;
    }

    void clear() {
        nodes.clear();
        nodes.emplace_back();
        lazy_xor = 0;
    }

    node_id insert(UInt value, int multiplicity = 1) {
        assert(valid_value(value));
        assert(multiplicity > 0);
        value ^= lazy_xor;
        node_id node = 0;
        nodes[node].count += multiplicity;
        for (int position = BitWidth - 1; position >= 0; --position) {
            const int direction = bit(value, position);
            if (nodes[node].child[direction] == null_node) {
                const node_id child = new_node();
                nodes[node].child[direction] = child;
            }
            node = nodes[node].child[direction];
            nodes[node].count += multiplicity;
        }
        return node;
    }

    int count(UInt value) const {
        assert(valid_value(value));
        const node_id node = find_node(value);
        return node == null_node ? 0 : nodes[node].count;
    }

    bool contains(UInt value) const {
        return count(value) > 0;
    }

    bool erase_one(UInt value) {
        assert(valid_value(value));
        if (!contains(value)) return false;
        value ^= lazy_xor;
        int node = 0;
        --nodes[node].count;
        for (int position = BitWidth - 1; position >= 0; --position) {
            node = nodes[node].child[bit(value, position)];
            --nodes[node].count;
        }
        return true;
    }

    bool erase(UInt value) {
        return erase_one(value);
    }

    int erase_all(UInt value) {
        assert(valid_value(value));
        const int multiplicity = count(value);
        if (multiplicity == 0) return 0;
        value ^= lazy_xor;
        int node = 0;
        nodes[node].count -= multiplicity;
        for (int position = BitWidth - 1; position >= 0; --position) {
            node = nodes[node].child[bit(value, position)];
            nodes[node].count -= multiplicity;
        }
        return multiplicity;
    }

    void xor_all(UInt value) {
        assert(valid_value(value));
        lazy_xor ^= value;
    }

    UInt kth_xor(int k, UInt value) const {
        assert(0 <= k && k < size());
        assert(valid_value(value));
        const UInt effective_xor = lazy_xor ^ value;
        UInt result = 0;
        int node = 0;
        for (int position = BitWidth - 1; position >= 0; --position) {
            const int preferred = bit(effective_xor, position);
            const int preferred_size = subtree_size(nodes[node].child[preferred]);
            if (k < preferred_size) {
                node = nodes[node].child[preferred];
            } else {
                k -= preferred_size;
                node = nodes[node].child[preferred ^ 1];
                result |= UInt(1) << position;
            }
        }
        return result;
    }

    UInt kth(int k) const {
        return kth_xor(k, 0);
    }

    UInt min() const {
        return kth(0);
    }

    UInt max() const {
        return kth(size() - 1);
    }

    UInt min_xor(UInt value) const {
        return kth_xor(0, value);
    }

    UInt max_xor(UInt value) const {
        return kth_xor(size() - 1, value);
    }

    int count_less_xor(UInt value, UInt upper) const {
        assert(valid_value(value));
        if (!valid_value(upper)) return size();
        const UInt effective_xor = lazy_xor ^ value;
        int result = 0;
        int node = 0;
        for (int position = BitWidth - 1; position >= 0 && node != -1; --position) {
            const int zero = bit(effective_xor, position);
            if (bit(upper, position) == 1) {
                result += subtree_size(nodes[node].child[zero]);
                node = nodes[node].child[zero ^ 1];
            } else {
                node = nodes[node].child[zero];
            }
        }
        return result;
    }

    int count_xor_less(UInt value, UInt upper) const {
        return count_less_xor(value, upper);
    }

    int count_xor_less_equal(UInt value, UInt upper) const {
        assert(valid_value(value));
        assert(valid_value(upper));
        if (upper == value_mask()) return size();
        return count_xor_less(value, upper + UInt(1));
    }

    int count_xor_greater(UInt value, UInt lower) const {
        assert(valid_value(value));
        assert(valid_value(lower));
        return size() - count_xor_less_equal(value, lower);
    }

    int count_xor_greater_equal(UInt value, UInt lower) const {
        assert(valid_value(value));
        assert(valid_value(lower));
        return size() - count_xor_less(value, lower);
    }

    int count_xor_range(UInt value, UInt lower, UInt upper) const {
        assert(valid_value(value));
        assert(valid_value(lower));
        assert(lower <= upper);
        return count_xor_less(value, upper) -
               count_xor_less(value, lower);
    }

    int order_of_key(UInt value) const {
        return count_less_xor(0, value);
    }

    int count_less(UInt value) const {
        return order_of_key(value);
    }

    int count_less_equal(UInt value) const {
        assert(valid_value(value));
        if (value == value_mask()) return size();
        return count_less(value + UInt(1));
    }

    int count_greater(UInt value) const {
        return size() - count_less_equal(value);
    }

    int count_greater_equal(UInt value) const {
        return size() - count_less(value);
    }

    std::vector<UInt> to_vector() const {
        std::vector<UInt> result;
        result.reserve(size());
        for (int k = 0; k < size(); ++k) {
            result.push_back(kth(k));
        }
        return result;
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Binary Trie
(ds/binary_trie/binary_trie.hpp)

Overview

Template Parameters

Methods

Example

Verified with

Code

Binary Trie (ds/binary_trie/binary_trie.hpp)

Overview

Template Parameters

Methods

Example

Verified with

Code

Binary Trie
(ds/binary_trie/binary_trie.hpp)