遅延評価 Binary Trie
(DataStructure/misc/LazyBinaryTrie.py)

• View this file on GitHub
• Last update: 2021-06-19 15:29:27+09:00

概要

Trie 構造で非負整数を管理するデータ構造。集合内の全要素に対する xor を行うことができる。

使い方

LazyBinaryTrie(MAX_BIT_LENGTH=32)
空の集合を構築する。集合に格納できる 2 進数での最大桁数を MAX_BIT_LENGTH (これを $\sigma$ とする) で指定する。計算量 $O(1)$

• __len__() -> int
  集合の大きさを返す。計算量 $O(1)$

• __contains__(val: int) -> bool
val が集合に属しているか返す。計算量 $O(\sigma)$

• add(val: int) -> bool
  集合に val を追加する。追加に成功した場合は True を、失敗した場合 (既に val が集合に属していた場合) は False を返す。計算量 $O(\sigma)$

• remove(val: int) -> int
  集合から val を削除する。削除に成功した場合は True を、失敗した場合 (val が集合に属していなかった場合) は False を返す。計算量 $O(\sigma)$

• kth_smallest(k: int) -> int
  集合内で k 番目 (0-indexed) に小さい要素を返す。計算量 $O(\sigma)$

• kth_largest(k: int) -> int
  集合内で k 番目 (0-indexed) に大きい要素を返す。計算量 $O(\sigma)$

• bisect_left(lower: int) -> int
  集合内で lower 以上の値が現れる最初のインデックスを返す。計算量 $O(\sigma)$

• bisect_right(upper: int) -> int
  集合内で upper よりも大きい値が現れる最初のインデックスを返す。計算量 $O(\sigma)$

• get_xor_min(val: int) -> int
  集合内の要素と val との bitwise-xor をとった場合に考えられる最小値を返す。計算量 $O(\sigma)$

• all_xor(val: int) -> None
  集合内の全要素に対して val の bitwise-xor を行う。計算量 $O(1)$

Verified with

• TestCase/AOJ/ITP2_7_C.LazyBinaryTrie.test.py
• TestCase/unittest/LazyBinaryTrie.unittest.test.py

Code

class LazyBinaryTrieNode:
    def __init__(self):
        self.bit0 = None
        self.bit1 = None
        self.lazy_val = 0
        self.size = 0


class LazyBinaryTrie:
    def __init__(self, MAX_BIT_LENGTH=32):
        self.MAX_BIT_LENGTH = MAX_BIT_LENGTH
        self.root = LazyBinaryTrieNode()

    def __len__(self):
        return self.root.size

    def __contains__(self, val):
        return self._search(val)

    def _propagate(self, ptr, i):
        lazy_val = ptr.lazy_val
        if (lazy_val >> i) & 1: ptr.bit0, ptr.bit1 = ptr.bit1, ptr.bit0
        if ptr.bit0 is not None: ptr.bit0.lazy_val ^= lazy_val
        if ptr.bit1 is not None: ptr.bit1.lazy_val ^= lazy_val
        ptr.lazy_val = 0

    def _search(self, val):
        ptr = self.root
        for i in reversed(range(self.MAX_BIT_LENGTH)):
            self._propagate(ptr, i)
            if (val >> i) & 1: ptr = ptr.bit1
            else: ptr = ptr.bit0
            if ptr is None: return False
        return True

    def add(self, val):
        if self._search(val): return False
        ptr = self.root
        ptr.size += 1
        for i in reversed(range(self.MAX_BIT_LENGTH)):
            if (val >> i) & 1:
                if ptr.bit1 is None: ptr.bit1 = LazyBinaryTrieNode()
                ptr = ptr.bit1
            else:
                if ptr.bit0 is None: ptr.bit0 = LazyBinaryTrieNode()
                ptr = ptr.bit0
            ptr.size += 1
        return True

    def remove(self, val):
        if not self._search(val): return False
        ptr = self.root
        ptr.size -= 1
        for i in reversed(range(self.MAX_BIT_LENGTH)):
            if (val >> i) & 1:
                if ptr.bit1.size == 1:
                    ptr.bit1 = None
                    return True
                ptr = ptr.bit1
            else:
                if ptr.bit0.size == 1:
                    ptr.bit0 = None
                    return True
                ptr = ptr.bit0
            ptr.size -= 1
        return True

    def kth_smallest(self, k):
        ptr = self.root
        res = 0
        for i in reversed(range(self.MAX_BIT_LENGTH)):
            self._propagate(ptr, i)
            szl = ptr.bit0.size if ptr.bit0 is not None else 0
            if k < szl:
                ptr = ptr.bit0
            else:
                res |= 1 << i
                k -= szl
                ptr = ptr.bit1
        return res

    def kth_largest(self, k):
        return self.kth_smallest(self.root.size - k - 1)

    def bisect_left(self, lower):
        ptr = self.root
        idx = 0
        for i in reversed(range(self.MAX_BIT_LENGTH)):
            if ptr is None: return idx
            self._propagate(ptr, i)
            if (lower >> i) & 1 == 1:
                idx += ptr.bit0.size if ptr.bit0 is not None else 0
                ptr = ptr.bit1
            else:
                ptr = ptr.bit0
        return idx

    def bisect_right(self, upper):
        return self.bisect_left(upper + 1)

    def get_xor_min(self, val):
        ptr = self.root
        res = 0
        for i in reversed(range(self.MAX_BIT_LENGTH)):
            self._propagate(ptr, i)
            if (val >> i) & 1:
                if ptr.bit1 is not None: ptr = ptr.bit1
                else:
                    ptr = ptr.bit0
                    res |= 1 << i
            else:
                if ptr.bit0 is not None: ptr = ptr.bit0
                else:
                    ptr = ptr.bit1
                    res |= 1 << i
        return res

    def all_xor(self, val):
        self.root.lazy_val ^= val

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page