sataniC++

C++、競プロ、数学などについて色々考えたりします。

ダブリング

概要

N個次の要素を知りたい」といった状況で頻繁に用いられるテクニックです。


使える状況

「ある要素に対してその次の要素は容易に得られるが、N個分次の要素を得るクエリがO(N)時間じゃ間に合わない」
というときに、ダブリングを使うことによって、全体の大きさMに対して準備O(M\log M)、クエリO(\log N)で求めることが出来ます。


説明

「使える状況」で述べた場面は、具体的には、

  • ある数XN乗を求めたい
  • 根付き木において、ある頂点vのN個上の親を知りたい

などです。

どちらも、次の要素(X^2や頂点vの親)は容易に求められますね。


しかし、次の次の次の…と初めの要素からN個次の要素を知るには、単純に考えるとO(N)時間がかかってしまいます。

これをO(\log N)時間で行うことが出来るのが、ダブリングと呼ばれる手法です。


ダブリングは、次のような流れで行います。
まずは各要素における「1つ次の要素」を調べておきます。
こうすることで、「「1つ次の要素」の1つ次の要素」、つまり「2つ次の要素」は即座に得ることが出来るようになります。

これを繰り返すと、各要素の「4つ次の要素」,「8つ次の要素」,…,「2^k個次の要素」と調べ上げることが出来ます。


このとき、k=\lfloor \log N \rfloorまで調べれば、あとはNを二進展開した時に立っているビットの数だけ
「...「○個次の要素」の●個次の要素...」と調べればよいため、
1N個次の要素を調べるのにはO(\log N)時間しかかかりません。
(ちなみに二進展開とは、2進数に変換することをいいます)


疑似(?)コード

ダブリングは適用できる範囲が広いため、大まかな流れを以下にC++風で記しておきます。
(基本的には\mathtt{next[ 0] }の値を計算するところを変えるだけです)

int N; // 全体の要素数
int LOG_N; // = floor(log_2(N))

// next[k][i]で、i番目の要素の「2^k個次の要素」を指す
// (なお、i番目の要素に対して「2^k個次の要素」が存在しないとき、
//  next[k][i]が指し示す要素番号を-1とします)
std::vector<std::vector<int>> next(LOG_N + 1, std::vector<int>(N)); 

// next[0]を計算
for (int i = 0; i < N; ++i){
    next[0][i] = (iの次の要素);
}

// nextを計算
for (int k = 0; k < LOG_N; ++k){
    for (int i = 0; i < N; ++i){
        if (next[k][i] == -1) {
            // 2^k個次に要素が無い時、当然2^(k+1)個次にも要素はありません
            next[k + 1][i] = -1;
        }
        else {
            // 「2^k個次の要素」の2^k個次の要素は、2^(k+1)個次の要素です
            next[k + 1][i] = next[k][next[k][i]];
        }
    }
}

// ----ここまで準備----

// p番目の要素の「Q個次の要素」を求めることを考えます
for (int k = LOG_N - 1; k >= 0; --k){
    if (p == -1) {
        // pがすでに存在しない要素を指していたら、
        // それ以降で存在する要素を指すことはないためループを抜けます
        break;
    }
    if ((Q >> k) & 1) {
        // Qを二進展開した際、k番目のビットが立っていたら、
        // pの位置を2^kだけ次にずらします
        p = next[k][p];
    }
}

コードの説明

上に示したコードは、次のような流れに沿って処理を行っています。

  • 各要素について、すぐ次の要素\mathtt{next[0]}を調べる
  • 各要素について、\mathtt{next[0]}を使って\mathtt{next[1]}を求め、その\mathtt{next[1]}を使って\mathtt{next[2]}を求め、…として\mathtt{next}全体を調べ上げる
  • 上で求めた\mathtt{next}を使って実際に\mathtt{p}番目の要素の\mathtt{Q}個次の要素を求める

具体例

ある根付き木に対して、頂点vからN回親を辿った先の頂点を求める

今回は、解説スライドを用意してみました。
(すべて画像で構成されているため若干見づらいかと思います。後でPowerPoint等で作り直します…)


備考

一般に、\mathtt{next}配列を構成するのに全体の大きさMとしてO(M\log M)時間がかかりますが、
ある数Xの累乗を求める際には、
「どんな要素(数)であってもK個次の要素はX^Kを掛けることに他ならない」
という性質から、\mathtt{next}配列を構成する必要がなく、各クエリごとのO(\log N)時間しかかかりません。


また、「二進展開する」とは言っていますが、上記コードで示している通り、
実際には「\mathtt{k}番目のビットが立っているか?」を調べるだけで構いません。


あとがき

ダブリングは、繰り返し自乗法LCA(最近共通祖先)を求める際、Suffix Array(接尾辞配列)の構成などなど、多くの場面で使われる考え方です。
これはアルゴリズムの高速化において、「数を二進展開して考える」ことが基本となっているためでしょう。
(他にも「半分に分割して考える」というのも基本的な考えの一つです)


ダブリング自体を意識して問題を解くことは多くはないかもしれませんが、
高速化の手法の一つとして頭に入れておくと良いでしょう。