±RMQによるLCAの実装

構築 O(n) 質問 O(1) のやつ。AOJ の以下の問題で verify した。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C

基本的には euler-tour + sparse table RMQ。euler-tour したときの深さ列が ±1 で変化することを利用して高速化する。

配列 a の sparse table RMQ を構築すると O(n log n) の空間が必要になってしまう。そこで配列 a をサイズ s=log(n)/(1+ε) のブロックに分割する。

ブロックをひとつの要素とみなし sparse table を構築。ブロックの数は n/s 個なので O(n) でできる。

次にブロック毎に sparse table を構築する、のかと思いきやそうはしない。配列 a は差が±1の列なので、+-+++-…のような二進列としてみなせる。 あらかじめ+++、++-、+-+、+--、-++…という全パターンの sparse table を構築しておく。これも O(n) になる。

よって全体で O(n)。log が多項式よりもオーダーが小さいことを利用して計算量を落としているため、εを上手く設定しないと実際の計算量は落ちない。

実用的に速いかは分からない。

参考