メインコンテンツまでスキップ

ダブリング

ダブリングとは​

ある要素の K 個先の移動先を高速で求めることができるアルゴリズムである。 前処理で移動先のテーブルを作成し、テーブルを用いて高速でクエリを処理する。

前処理には全要素を N とし、K 個先の要素を求める場合は O(N log(K)log(K))で求めることができ、 クエリに対しては O(log(K)log(K))で求めることができる。

ダブリング

アルゴリズム​

流れ​

前処理として、ある要素の2n2^{n}先の要素を計算しておく必要がある。 これは 2 進数の性質をうまく活用することで綺麗に記述することができる。

ダブリングを使った例として LCA(Lowest Common Ancestor)を考える。 LCA はある 2 つの要素の共通の親(深さが小さい)の中で一番近い(深さが大きい)親を探すものである。

以下のような木を考える。

ダブリング例1

このような木の k 個前(親)の木を求める。初めに 1 個前の親を求める。 親が存在しないものには-1 を代入し、存在しないことを表す。 1 個前の親は深さ優先探索や幅優先探索を用いることで簡単に求めることができる。

1個前の親

1 個前の親の 1 個前の親は 2 個前の親であるため、2 個前の親も上の表を活用することで簡単に求めることができる。

2個前の親について

そのため、2 個前の親は次のようになる。

2個前の親

同様な考え方で 4 個前の親を求めることができる。

4個前の親について

4 個前の親を求めると次のようになる。

4個前の親

同様に 8,16 個前の親を求めると次のようになる。

16個前の親

これ全ての要素の2n2^n個前の親要素を求めることができる。

ここまでが前処理の部分である。

次はこの表を活用して、2 つの要素の LCA を求めることを考える前にこの表を使用して、5 番目の要素の 3 つ前の親が何かを考えてみる。

3 つ前の親要素については求めていないが作成した表から導出が可能である。 3 は2 + 1 = 3と分解することができるので、2 つ前の親の 1 つ前の親が 3 つ前の親であることがわかる。 そのため、5 番の 2 つ前の親は表から 2 番の要素であることがわかる。さらに 2 番の 1 つ目の親は 0 番であることもわかるので 5 番目の 3 つ前の親は 0 番であるということが分かる。 これは 3 を 2 進数で表すと11(2)11_{(2)}となるので、1 となっている部分で要素を移動させる良い。

備考

LCA では要素の深さ番号を使用する。これは前処理の 1 つ前の親を求める際の幅優先探索等をする際に一緒に深さを求めておく。 今回の場合は次のようになる。 深さ

LCA の求めるには以下の順番で処理を行う。

  1. 対象要素の深さを揃える
  2. 前処理で作成した表を用いて共通の親を探す。

2 つの要素の LCA を求める例題として、3 番と 7 番の LCA を求めてみる。 まずは手順 1 の要素の深さを揃えることを考える。 これはともに深さが 2 なので、行う必要がない。

次に手順 2 を考える。 前処理で作成したテーブルを使用し、それぞれの N 個前の親要素を調べる。

初めに 16 個前の親を比較すると、ともに-1となり、2 つの要素で一致している。これは 16 個前までのどこかで共通要素を持っていることがわかるので、戻り過ぎだと分かる。 同様に 8,4,2 個前の要素も一致しているので戻り過ぎていることがわかる。

1 個前の要素は別々の要素なので、次の検索する基準要素を 1 個前の親要素に変更する。 そうするとそれぞれ、1,2 となる。

全ての前処理で作成したテーブルの要素を確認し終えた時点で検索対象としている基準の要素 2 つの 1 個前の親要素が共通親の中で一番近いものとなっている。 そのため、1 番,2 番の要素の親要素である 0 番が LCA となる。

要素変更

次に 10 番の要素と 16 番の要素の LCA を考える。

10 番の要素は深さが 5 であり、16 番の要素は 6 であり、異なっているので深さを合わせる手順 1 を行う必要がある。 深さを合わせるため、6 - 5 = 1で 16 番の要素を 1 個前の親要素にする必要がある。 前処理作成したテーブルを使用すると 16 番の 1 個前の親は 14 番の要素となる。

手順 2 では 10 番の要素と 14 番の要素の共通の親要素を持たないギリギリの親要素を求める。

先ほどと同様に 16 個前の親要素から見ていくと次のようになる。

要素変更2

同様に 1 番の親要素である 0 番が LCA となる。

プログラム​

前処理​

1 つ前の要素を求める部分は幅優先探索等を使用することで簡単に求めることができるので割愛し、2,4,8,16 個前の要素を求める処理は 以下のように書くことで求めることができる。

ここではlca_box[i][j]のiは2i2^{i}個前の要素かを表し、jは要素番号であり、値は遷移先の要素番号である。 つまり、lca_box[i][j]に N が格納されているとすると、j 番目の要素の2i2^{i}個前の要素は N となる。 lca_box[0][j]に値を格納する部分が深さ優先探索・幅優先探索を用いて埋める必要がある。

count は2i2^{i}で求めたい乗数の値であり、n は要素数となる。

# 前処理で求めておく2^Nを求める
m = 1
count = 0
while m < len(tree):
    m <<= 1
    count += 1

lca_box = [[-1] * (len(tree) + 1) for _ in range(count+1)]

# 幅優先探索で深さを求める
depth = [-1] * len(tree)
q = deque()
q.append(0)
depth[0] = 0
while len(q) != 0:
    pos = q.popleft()
    for to in tree[pos]:
        if depth != -1:
            lca_box[0][to] = pos
            depth[to] = depth[pos] + 1
            q.append(to)


for i in range(1, count+1):
    for j in range(len(tree)):
        lca_box[i][j] = lca_box[i-1][lca_box[i-1][j]]

ここでポイントとなっているのは

lca_box[i][j] = lca_box[i-1][lca_box[i-1][j]]

である。4 個前の前の要素を求める際に 2 個前の要素を活用したように[lca_box[i-1][j]で求めたい N 個前の要素のN2\frac{N}{2}個前の要素の遷移先要素を取得し、 その取得した要素の遷移先が N 個前の要素の遷移先となるため、lca_box[i-1][lca_box[i-1][j]]となっている。

クエリ​

手順 1 の深さを揃える処理は次のようになる。

depth には前処理段階で深さを求めたものが格納されており、depth[i]で i 番目の要素の深さを取得することができる。

def ancestors(u, up):
    cnt = 0
    while up != 0:
        if up & 1 == 1:
            u = lca_box[cnt][u]
        cnt += 1
        up >>= 1
    return u


check = [
    (3, 7),
    (10, 16),
    (11, 15),
    (2, 3)
]
for u, v in check:
    # 常にu側に深さが深い方を配置
    if depth[u] < depth[v]:
        u, v = v, u

    # 手順1 深さを合わせる
    up = depth[u] - depth[v]
    u = ancestors(u, up)

    # u,v自身が共通の要素となる場合があるので確認
    if u == v:
        print(f"u: {u}, v:{v}")
        continue

次に手順 2 は次のようになる。 count は前処理で使用したものと同じである。

# 手順2 親を遡る
for i in range(count, -1, -1):
    nextu = lca_box[i][u]
    nextv = lca_box[i][v]
    # 一致しない場合のみ要素を更新
    if nextu != nextv:
        u = nextu
        v = nextv

# 最終結果の1つ前がLCAとなる
print(f"u: {lca_box[0][u]}, v:{lca_box[0][v]}")

上記の例を全コードは以下となる。

doubling.py
from collections import deque
tree = [
    [1, 2],
    [7],
    [3, 4],
    [5],
    [6],
    [],
    [8],
    [9],
    [10, 11],
    [12],
    [15],
    [13],
    [14],
    [],
    [16],
    [],
    []
]

# 前処理で求めておく2^Nを求める
m = 1
count = 0
while m < len(tree):
    m <<= 1
    count += 1

lca_box = [[-1] * (len(tree) + 1) for _ in range(count+1)]

# 幅優先探索で深さを求める
depth = [-1] * len(tree)
q = deque()
q.append(0)
depth[0] = 0
while len(q) != 0:
    pos = q.popleft()
    for to in tree[pos]:
        if depth != -1:
            lca_box[0][to] = pos
            depth[to] = depth[pos] + 1
            q.append(to)


for i in range(1, count+1):
    for j in range(len(tree)):
        lca_box[i][j] = lca_box[i-1][lca_box[i-1][j]]


def ancestors(u, up):
    cnt = 0
    while up != 0:
        if up & 1 == 1:
            u = lca_box[cnt][u]
        cnt += 1
        up >>= 1
    return u


check = [
    (3, 7),
    (10, 16),
    (11, 15),
    (2, 3)
]
for u, v in check:
    # 常にu側に深さが深い方を配置
    if depth[u] < depth[v]:
        u, v = v, u

    # 手順1 深さを合わせる
    up = depth[u] - depth[v]
    u = ancestors(u, up)

    # u,v自身が共通の要素となる場合があるので確認
    if u == v:
        print(f"u: {u}, v:{v}")
        continue

    # 手順2 親を遡る
    for i in range(count, -1, -1):
        nextu = lca_box[i][u]
        nextv = lca_box[i][v]
        # 一致しない場合のみ要素を更新
        if nextu != nextv:
            u = nextu
            v = nextv

    # 最終結果の1つ前がLCAとなる
    print(f"u: {lca_box[0][u]}, v:{lca_box[0][v]}")

参考​