binary Trieによるbit列索引
整数を上位bitから分岐するTrieへ格納し、XOR・大小・距離条件に合う候補をbitごとに選ぶ。
この典型を扱う単元: bit列をTrieで索引化する
検索別名: 01-Trie、XOR Trie、bitwise trie
未知問からこの典型を見つける手掛かり
- 扱う対象
- bit列
- xor
- 上位bit
- 整数集合
- 使う手掛かり
- bitごとに分岐
- xorを最大
- xorを最小
- 二進Trie
- 保つ不変量
- 0と1の子
- 共通上位bit
- 部分木の要素数
- 求めるもの
- k番目
- 最大xor
- 最小xor
- 条件を満たす整数
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
学習成果と学習単位
整数を上位bitからTrieへ格納し、部分木情報を保ちながらXOR・大小条件に最適な分岐を選べる。
bit列をTrieで索引化するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。