整数は0と1からなる文字列だよ派です(計算機モデルとしてWord-RAMを仮定). この記事は文字列アルゴリズム Advent Calendar 2017 17日目の記事です. vEB木と並んで高速にpredecessorを解くデータ構造y-fast trie1を紹介します. 文字列のキーワード索引などでよく利用されるトライ構造(Trie)で整数集合を管理する面白いデータ構造です. Predecessor Dictionary Problem 全体集合$U = \{ 0, \ldots, u-1 \}$の部分集合$S \subseteq U$に対して,以下のクエリをサポートするデータ構造をpredecessor dictionaryといいます. $\mathit{Predecessor(x)}$: $x$以下の$S$の要素で一番大きいものを返す. $\mathit{Successor(x)