データ構造をマージする一般的なテクを高速化するやや一般的なテク

知る人ぞ知る謎の知識みたいになってる気がしたのでメモ。

サイズ $A$ とサイズ $B$ のデータ構造 ($A < B$) が $O(A \log B)$ 時間でマージできる場合、合計 $O(N \log ^2 N)$ 時間で $N$ 個の要素がマージできます。競プロだと std::set や std::priority_queue などです。

ここで、もしもマージが $O(A (\log B - \log A + 1))$ に高速化できたならば、合計の計算量が $O(N \log N)$ になります。証明は普通のデータ構造をマージする一般的なテクとほぼ同じで、ある要素を含むデータ構造のサイズが $1 \to x \to y \to N$ と成長したなら、この要素にかかる計算量は $(\log x - \log 1 + 1) + (\log y - \log x + 1) + (\log N - \log z + 1) = O(\log N)$ 、といったノリです。

でも$O(A (\log B - \log A + 1))$ なんて謎の計算量なんて…と思うかもしれませんが、実はかなり多くのデータ構造がこの計算量を達成できます。すごいですね。

平衡二分木の merge / split が登場してややこしいので、データ構造をマージする操作を meld と呼ぶことにします

二分ヒープ

std::priority_queue の中身です。(自分で std::priority_queue 相当のものを実装する必要がありますが)実はpriority_queue + マージテクは $\log$ 一個です。でも $O(N \log ^2 N)$ のマージがそもそも爆速だからうまみが少なそう。

まず、二分ヒープを線形時間で構築するアルゴリズムを理解する必要があります。たとえば下のコードのようになります。

void down_heap(vector<int>& d, int u) {
    int n = int(d.size());
    while (2 * u + 1 < n) {
        int v = (2 * u + 1);
        if (v + 1 < n && h.d[v] < h.d[v + 1]) v++;
        if (h.d[u] >= h.d[v]) break;
        swap(h.d[u], h.d[v]);
        u = v;
    }
}

void build_heap(vector<int>& d) {
    int n = int(d.size());
    for (int i = n - 1; i >= 0; i--) {
        down_heap(d, i);
    }
    return h;
}

「ある頂点について、葉の方向に自分より大きい要素とswapしていく」down_heap関数を、葉から順に全ての頂点に呼ぶと二分ヒープが構築できます。計算量は各頂点の「葉までの距離」の総和になり、式をコネコネすると線形時間であることがわかります。

meld関数のコードは次のようになります。

void meld(vector<int>& h, vector<int>& other) {
    if (h.len() < other.len()) swap(h, other);
    if (other.empty()) return;

    int l = int(h.size()), r = l + int(other.size()) - 1;

    h.insert(h.end(), other.begin(), other.end());

    while (l) {
        l = (l - 1) / 2;
        r = (r - 1) / 2;
        for (int i = r; i >= l; i--) {
            down_heap(h, i);
        }
    }
}

これは何をしているのかというと、小さいほうのヒープの要素を適当に大きいヒープの末尾に追加した後、「新しく追加した要素を子孫に持つ要素」全てに対して先述のdown_heap関数を呼んでいるだけです。計算量ですが、各頂点についてmin(other.size(), 葉までの距離)であること、そしてこれの総和が上記の $O(A (\log B - \log A + 1))$ になることが示せます。

std::set (by merge-split baseの平衡二分木)

std::setも、自作の平衡二分木で実装することで $O(A (\log B - \log A + 1))$が達成できます。まず、一般に merge-split base の平衡二分木ならなんでも可能な(ハズの)方法を紹介しますが、おそらく定数倍はとても悪いです。

$A \le \sqrt{B}$ の場合は愚直に $A$ 回 insertすればよいので、$\sqrt{B} < A$ としてよい。

サイズ $B$ の木をサイズ $B / A$ (ぐらい)の木に $A$ 分割する。
- 愚直にsplitを使うと $O(A \log B)$ だが、例えば8分割したいなら (2分割 => それぞれを2分割 => それぞれを2分割)、のように、なるべくsplitする木のサイズが小さくなるように切っていくと $O(A (\log B - \log A + 1))$ になる
分割した木それぞれに対して、サイズ $A$ の木の(対応する値の範囲の)要素を追加していく
- 追加する要素が $B / A$ 個以下なら愚直にinsert
- 追加する要素が $B / A$ 個以上なら(両方の木をvectorにする) => (std::merge) => (vectorを長さ $B / A$ のブロックに分割する) => (それぞれのブロックから、線形時間で新しい木を構築する)で、線形時間でマージする
分割した木たちを(splitと同様に、いい感じに)マージして新しい木を作る。
- サイズが $(B / A)$以上$2(B / A)$以下の木たちのマージになり、splitと同様の計算量解析が可能

で$O(A (\log B - \log A + 1))$ になっている…ハズ

std::set (by merge-split baseの多くの平衡二分木)

葉にだけ値を持たせる赤黒木など、サイズ $L, R (L < R)$の木のmerge (not meld)が $O(\log R - \log L + 1)$であることが保証可能な平衡二分木は割と簡単に実装できます。(参考: https://www2.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day4-copypaste-slides.pdf) このような平衡二分木なら、次のような割と素朴なmeld関数が上手くいくはずです。

Node* meld(Node* n, deque<int>& q) {
    while(q.size() && q.front() == n->val) q.pop_front(); // multisetにしたい場合はこの行を消す
    if (n->val < q.front()) return n;
    if (is_leaf(n)) {
        vector<int> v;
        while (q.size() && q.front() < n->val) {
            v.push_back(q.front()); q.pop_front();
        }
        return merge(build_tree(v), n); // build_tree(v): |v|時間で木を構築する関数
    }
    Node* l = meld(n->l, q);
    Node* r = meld(n->r, q);
    return merge(l, r); // (1)
}

Node* meld(Node* n, Node* m) {
    if (n->size < m->size) swap(n, m);
    deque<int> q = to_deque(m); // to_deque(m): mの要素を舐めて(sortedな)dequeを線形時間で生成する関数
    n = meld(n, q);
    return merge(n, build_tree(q));
}

まず、meld関数が呼ばれる回数は、n->sizeが $B / A$以上かどうかで場合分けすれば示せます。

n->size が $B / A$ 以上 : そもそもこういう頂点は $O(A)$ 個しかない
n->size が $B / A$ 未満: 高さが $O(\log (B / A)) = O(\log B - \log A + 1)$ なので合計 $O(A (\log B - \log A + 1))$

コード中の(1)の部分の計算量が本質です。ここで、merge関数の計算量により、meld前後で木のサイズが $k$ 倍に増えていたら (1) の部分の計算量が $O(\log k)$ であることを利用します。

木のサイズが $2$ 倍以上に増えるような頂点数は？: 高々 $O(A)$
木のサイズが $4$ 倍以上に増えるような頂点数は？: 高々 $O(A / 2)$
:

より、(*)の部分の計算量の合計は(meldが呼ばれた回数に加えて)高々 $O(A)$ です。

std::set (by splay-tree)

は愚直に小さいほうの集合を昇順(or 降順)にinsertしていくだけで $O(A (\log B - \log A + 1)$ って噂を聞いたんですが、本当かわかりません。

std::set (by treap)

は割と容易に $O(A (\log B - \log A + 1)$ のmeldが書けるって聞きました。いかがでしたか