Trie木 (Binary Trie)
文字列リストを管理するとき、メモリ・検索速度的に優れたデータ構造。
辺に文字を対応させた根付き木で、根からのパスで通った辺によって単語を表現する。
- 前方一致検索が出来る
- 辞書順最小・最大の検索、$k$ 番目の検索が素早くできる（各ノードに自身の部分木に含まれる単語数を持たせる）
- ある単語の直前・直後の単語検索ができる
- 互いに似ている多数の短い文字列の管理に特に向く
- 少数の長い文字列の管理もできるが、パフォーマンスは落ちる。それにはパトリシア木などを用いる
- 辞書的順序が変化しても最大最小や $k$ 番目を検索できる
一方、二分探索木やBinaryIndexedTreeのようにindexと親子関係を綺麗に対応させることはできないので、データ全体を1次元配列で持つのはできない。 Nodeクラスを量産して各インスタンスに親子関係を持たせるタイプの実装となる。
Pythonではクラスは読みやすいコードにはなるが生成コストが重い（と思う、要確認だが）ので、速度を気にするなら配列や辞書をインスタンス替わりに使う実装となる。
目的によって、ノードに持たせる値や実装方法にはある程度バリエーションがある。
Binary Trie
Trie木の辺の値を文字でなく0/1に限定し、非負整数を2進数で管理できるようにしたのがBinary Trie（二分トライ木）。
処理できるクエリと計算量は、管理する値の2進数での最大桁数を $d$ として、
- 値の挿入: $O(d)$
- 値の削除: $O(d)$
- 値の各種検索: だいたい $O(d)$
整数の大小比較に用いるには桁数を固定する（足りない桁は先頭をゼロで埋める）必要がある。 競技プログラミング的には長さを固定せずに「0と1だけから成る文字列の辞書的順序」の管理も出来る、一応。
$最大桁数 \times 値の個数$ 個のNodeインスタンスが最悪作られるので、2秒程度の処理で済ませるには、それが $10^6～10^7$ に収まっていればよい。 実際は、根に近い方のNodeはほぼ共有されるので、もうちょっと少なくなる。
最大や最小の管理や、ある値以下の最大の値検索(lower_bound)など、単独のクエリだけならheapqやbisectなどで事足りる。
使い道としては、それらの複合クエリを処理したいときか、またはビット演算と相性がいいのでそれと組み合わせた最大/最小を取得したいときになる。
- 最大値、最小値クエリ
- ある値以下の最大値、ある値以上の最小値クエリ
- 整数 $X$ のビット演算（andやxor）を取った後での最大値/最小値クエリ
特に全体にxorをかける操作は、即座にも、遅延評価でも行える。（'1'が立っているビットの左右の子を入れ替えればよい）
また、高速化としては、行き先がもはや1つに決まった枝は、葉までスキップできるようにしておく方法がある。 全ての値をinsertしてからクエリが来る場合は、insert後に1回探索してショートカットを貼ればよい。 insert,deleteとクエリが順不同に来る場合は、若干処理が面倒になるが、まぁ頑張れば出来る。（ほんとか？）
class BinaryTrie:
def __init__(self, bit_depth):
self.root = [None, None, 0] # [0-child, 1-child, count]
self.bit_start = 1 << (bit_depth - 1)
self.xor_mask = 0
def insert(self, x):
"""xを格納"""
b = self.bit_start
node = self.root
node[2] += 1
while b:
i = bool(x & b)
if node[i] is None:
node[i] = [None, None, 1]
else:
node[i][2] += 1
node = node[i]
b >>= 1
def pop_min(self):
"""xor_mask適用後の最小値を、適用前の値で取得し、木からは削除"""
b = self.bit_start
node = self.root
m = self.xor_mask
ret = 0
node[2] -= 1
while b:
i = bool(m & b)
if node[i] is None:
i ^= 1
ret = (ret << 1) + i
if node[i][2] > 1:
node[i][2] -= 1
node = node[i]
else:
tmp = node[i]
node[i] = None
node = tmp
b >>= 1
return ret
逆Binary Trie
ちょっと特殊だが、上位桁でなく、1の位から順に構築したTrie。
管理する2進数での最大桁を $d_{max}$ として、
- 値の追加: $O(d_{max})$
- 値の削除: $O(d_{max})$
- 値の検索: $O(d_{max})$
- 全体に特定の値をXORする操作: $O(d_{max})$
- 大小比較はできなくなる
- 代わりに、全体に1を足す操作を $O(d_{max})$ でできる
たくさんの値に、同時にXORや1を足す操作を行った後、各値がそれぞれ何になっているか、を高速に得たい場合に使える。
構造
$d_{max}$ は、「+1されて繰り上がりが発生した後」も含めての最大桁であることが望ましい。
その上で、先頭の'0'も省略せず、値は全て深さ $d_{max}$ のノードで存在を管理する。
（先頭の'0'を省略し、途中のノードに値の存在有無を持たせる実装もできるとは思うが、先頭の'0'があるかないかの二重登録の防止など、ややこしくなりそう）
○
0／ ＼1
○ ○
0／ \1 0/ ＼1
○ ○ ○ ○
0/\1 0/\1 0/\1 0/\1
⓪④ ②⑥ ①⑤ ③⑦
000 010 001 011
100 110 101 111
XORや1を足す操作は、既存のTrie構造を変えること無く、 各ノードから左右に伸びる辺のどちらが0でどちらが1か、をswapするだけで表現できる。
以下の2箇所で、0-1のswapフラグを管理する。
- 階層に対するswap状況を管理する、長さ $d_{max}$ のbool配列 $W=(W_0～W_{dmax-1})$
- ノードごとに、自身の直下の0-1のswap状況を管理するbool変数 $D_i$
操作
値の検索
根ノードから辿り、検索したい値 $X$ の下位から照合していく。
現在いるノード $i$ の、階層のswapフラグ $W_d$ と、ノード固有のswapフラグ $D_i$ をあわせたもの $W_d \oplus D_i$ が、次の子に遷移する際のswapフラグとなる。 これに従って $X$ に対応する子に遷移することを繰り返し、深さ $d_{max}$ までたどれたら存在有無がわかる。
追加・削除も似たような感じで行える。
全体にXOR
これは単純に、$W$ にXORを反映させればよい。
1を足す
根ノードからスタートし、$W_d \oplus D_i$ によってどちらの枝が0-1を表すかを確認しながら子を辿るのは検索と同じ。
たとえば根ノードについては、1を足すと、0の枝は1になり、1の枝は0になった上で次の桁へ繰り上がる。
つまり、swapされることになる。
（足す前の）1の枝を辿り、同じことを繰り返していく。
(例)1を足す前の状態
○
0／ ＼1
○ ○
0／ \1 1/ ＼0
○ ○ ○ ○
0/\1 1/\0 0/\1 0/\1
⓪④ ⑥② ③⑦ ①⑤
1を足した後の状態
○
[1／ ＼0] [ ] swapしたノード
○ ○
0／ \1 [0/ ＼1]
○ ○ ○ ○
0/\1 1/\0[1/\0]0/\1
①⑤ ⑦③ ④⓪ ②⑥
(⑧)
⑧に関しては、オーバーフローして⓪になっている（こういうことを防ぐため、$d_{max}$ はそれを含めての最大桁を設定した方が良い）が、他は、きちんと1ずつ足された状態が表現できていることがわかる。
最初に $a$ だった値が今何になっているか
根ノードから子をたどるのは値の検索などと一緒。
どちらの子を辿るかを、初期状態での枝に従うところが異なる。
初期状態（下図で言うなら、左の枝が0、右の枝が1）だとして、$a=3$ なら、右、右、左と辿っていくことになる。
○
0／ ＼1
○ ○
0／ \1 0/ ＼1
○ ○ ○ ○
0/\1 0/\1 0/\1 0/\1
⓪④ ②⑥ ①⑤ ③⑦
その上で、swapフラグを確認しながら、現在の値を復元していく。
もし、右、右、左と辿ったところの枝が、現在は 0,1,1 となっていたら、現在の値は6となっていることがわかる。
途中で $a$ として追加した値が今何になっているか
上記の応用だが、追加時に、「もし枝の値が全て初期状態だったら、何の値を表す箇所に追加したか」を記録しておく。
