ダブリング
概要
全体の要素数が \(N\) 個あって 1 回移動/操作した時にどの状態に遷移するのか定まっているとき、「\(K\) 個先の要素を求めるのに \(O(K)\) かかる」ような状態において、
- 前処理: \(O(N log K)\)
- クエリ: \(O(log K)\)
で計算を行うことができるようにするアルゴリズム。繰り返し二乗法もダブリングの一種と考えることができる。
アルゴリズム
ダブリングによる \(K\) 個先の要素の求め方:
- 前処理: \(\textrm{doubling}[k][i]\): 「\(i\) 番目の要素から \(2^k\) 先の要素は何か」を以下のように計算する。
- \(\textrm{doubling}[k+1][i] = \textrm{doubling}[k][\textrm{doubling}[k][i]]\)
- クエリ: 前処理した結果を利用して \(k\) 個先の要素を求める。
- 現在地を now として \(K\) を 2 進数として見た時のすべての桁について以下を行う。
(\(K = a_12^1 + a_22^2 + ... + a_x2^x\) のように 2 進数で表せる。前処理で各 \(2^i\) の時の結果はすぐにわかる)- \(K\) の \(k\) 桁目が 1 ならば \(now=\textrm{doubling}[k][now]\) とする。
- 現在地を now として \(K\) を 2 進数として見た時のすべての桁について以下を行う。