LOUDSの基本事項

LOUDSとは木を表現する簡潔データ構造の一つである。
以下のリンクの練習問題を全て解いたらLOUDSについての理解が進んだので、それについて簡単にメモしておく。
情報系修士にもわかるLOUDS

※ノード番号とは、木を根から（左の子優先の）BFSで辿った順番であり、indexとはビット列を配列に例えた際の添字番号の事である。
※また、rankとselectは簡潔データ構造の基本操作であるが、それらは言葉で軽く説明している
※以下特に言及しない限り1と0はビットを意味する

1. LOUDS bit string (LBS、要するにただのビット列)「10」から成るスーパールートであるノード番号0を入れる
2. 0が親ノードの区切りである。
3. 子ノードの数だけ1を列挙した後、0を入れる。

子ノード番号intから親ノード番号を取得する方法：

子ノード番号intからindexは「左から数えてint番目の1が立っているindex」すなわち、子ノードindex = select(1, 子ノード番号int)
子ノードindexから親ノード番号は「左に何個0があるか」すなわち、親ノード番号 = rank(0, 子ノードindex)

親ノード番号xから子ノード番号を取得する方法：

1. 左からx番目の0のindexを取得する、すなわち index = select(0, x)
2. その次のindexから1が続く限り列挙する
それぞれの子ノードindexからそのノードの番号は「左から数えて自分自身を含めて何個1が立っているか」すなわち、子ノード番号= rank(1, 子ノードindex) + 1

LOUDSは木を表現するので、一つの子に対しては一つの親しか存在しない。そのため、エッジに関する情報は、子ノードにそのまま格納して良い。
Trie木は各エッジが文字に対応している。そのため、補助配列を用いればLOUDSでTrie木を実現することができる。

例：
（汚い手書きは気にしないでください。。。Keynoteを覚えるべきですね。。。）

LOUDSによる木の表現：

親ノード番号	0	1	2	3	4	5	6	7	8	9	10	11
LBS	10	1110	10	0	1110	0	0	10	110	0	0	0

補助配列：

ノード番号	0	1	2	3	4	5	6	7	8	9	10	11
文字	なし	なし	i	a	l	n	a	i	b	e	l	s