bit列をTrieで索引化する

概要

binary Trieによるbit列索引

整数を上位bitから分岐するTrieへ格納し、XOR・大小・距離条件に合う候補をbitごとに選ぶ。

観察: bit bでXORが0になる候補があれば、XORが1になる候補の下位bitを全て0にしても優劣は逆転しない。2^b>2^b-1だからである。

設計: W bitに幅を揃えてAをTrieへ挿入し、各部分木の要素数を保つ。query xは上位bitから、xと同じbitの子が非空ならそこへ、空なら逆の子へ進んで答えに2^bを加える。

例: A={1,6}, x=3を3 bitで考える。最上位は0側の001を選び、結果は011 XOR 001=010、すなわち2。反対側110とのXORは5である。構築O(NW)、一query O(W)。

大小queryへの接続: x XOR a<Kの個数を求める。Kのbitが1ならXORのbitを0にする子の個数を全て加え、1にする子で等号prefixを継続する。Kのbitが0なら0にする子だけを辿る。最後の等号は数えない。

境界: 空の子へは進まず、重複は部分木個数に重ねて数える。ABC425 Gではこの同じ分岐をxの区間全体へ共有する。

考え方

整数を上位bitから二分木へ入れ、部分木の個数を持つ。XOR最小・最大queryでは希望するbitへ進み、そこに要素がなければ反対側へ進む。

根と各子に通過要素数を持ち、挿入はB bitを高位からたどって数を一増やし、削除は存在を確認して同じpathを一減らす。count=0の枝は無いものとして扱う。XOR最大はqueryのbitと逆の枝を優先、最小は同じ枝を優先する。高位で一度有利なら低位全体より寄与が大きいのでgreedyで正しい。選んだbitを蓄積すれば相手の実値も復元できる。

x XOR y<Kの個数では高位から「ここまでKと同値」を保つ。Kのbitが1ならXOR bit0の枝の全countを答えへ加え、XOR bit1の枝へ降りる。Kのbitが0ならXOR bit0の枝だけへ降りる。最後の同値pathは厳密不等号なので加えない。枝が空なら停止する。K≤0は0、K≥2^Bは全要素数として先に扱う。

成立条件と計算量

bit数Bなら挿入・削除・query O(B)、N要素でO(NB)節点。空部分木、重複値、符号付き整数の表現を固定する。XORが閾値未満の個数は、上位prefixが小さくなる枝を集計する。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。整数の大小とXORを上位bitからの分岐に写して検索する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-binary-trie

習得する技能

  • 整数を上位bitからTrieへ格納し、部分木情報を保ちながらXOR・大小条件に最適な分岐を選べる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

整数を上位bitから分岐する列として格納し、XOR・大小・最小距離の候補を貪欲に選ぶ。

このUnitでは扱わないもの

  • 文字列の共有接頭辞を索引化するTrie、および集合bitmaskの部分集合DP。

根拠