はじめに、この解説において、Static top treeとは公式解説と同じものを指すこととします。

Static top treeの構築は、ある程度の自由度が残されています

• rakeでclusterをまとめる部分
  • compressでまとめる部分と違い、殆ど全ての場合において子の順序を自由に入れ替えてよい
• compressでclusterをまとめる部分
• HL分解自体の自由度: 例えば、有名な自由度として 部分木のサイズが全て半分未満になったときに、そこで打ち切るか or 潜れるだけ潜るか がある

公式解説では、HL分解として最も大きい部分木に潜れるだけ潜る戦略を採用し、compress / rakeのマージ戦略として

• 完全二分木状にマージすれば全体で \(O(\log ^2 N)\)
• 「cluster が含む頂点数ができるだけ左の子と右の子で等しくなるようにマージする」という戦略を取れば全体で \(O(\log N)\)

ということを述べています。では、他に \(O(\log N)\)を達成する戦略は無いのでしょうか？

より直接的に、「Static top treeの葉の深さの最大値を最小化」するという方針で戦略を考えることにします。

rakeのマージ戦略

まず、(子の順序を自由に入れ替えられると仮定し)rakeのマージ戦略について考えます。なお、入れ替えられない場合には次に説明するcompressのマージ戦略も使用可能です。

rakeのマージ戦略については次の問題を解きたくなります。

長さ\(M\)の非負整数列 \(d_1, d_2, \cdots, d_M\)が与えられる。次の操作を \(M - 1\) 回行い、最後に残る要素の値を最小化せよ

• 数列の\(2\) つの要素 \(d_a, d_b\) を好きに選ぶ。それらを削除したのちに、\(\max {(d_a, d_b)} + 1\)を追加する。

実際に、 rakeを行うときに、各部分木の最大の葉までの深さを \(d_i\) として上記の問題を解き、そのマージ過程で木を作る戦略が考えられます。

この問題は、\(\sum 2^{d_i}\) が操作前後で減少しないことに注目すると、少なくとも \(\sum 2^{d_i} \le 2^{\mathrm{answer}}\)が最初の時点で成立する必要があることがわかり、これにより答えの下界が得られます。逆に「同じ値の要素が存在したらマージする」を繰り返し、最後に残った要素を小さい順にマージする戦略がこの下界を達成します。

また、証明は省きますが、「最小の要素を2つ選び、マージする」を繰り返すハフマン符号のような戦略もこの下界を達成します。

priority_queueを使って実装すると計算量は \(O(M \log M)\) となり、Static top treeの構築全体での計算量は素直には \(O(N \log N)\) となります。おそらくもっと正確に解析すると \(O(N)\) であることが言えると思いますが、bit演算を使用することでも高速化可能です。

実際にbit長をwとして

• 値が \(O(w)\) の要素をpush
• 値が最小の要素をpop

をそれぞれ \(O(1)\) で実行可能なデータ構造が設計可能です。今回は数列の値が木の深さに対応している = 高々値域が \(O(\log n)\)なので、\(w = \Omega(\log n)\) を仮定すれば計算量を \(O(M)\)、つまり構築全体で \(O(N)\) にすることが出来ます。

compressのマージ戦略

次に、compressのマージ戦略について考えます。compressのマージ戦略については次の問題を解きたくなります。

長さ\(M\)の非負整数列 \(d_1, d_2, \cdots, d_M\)が与えられる。次の操作を \(M - 1\) 回行い、最後に残る要素の値を最小化せよ

• 数列の隣り合う要素 \(d_i, d_{i + 1}\) を好きに選び、それを\(\max {(d_i, d_{i + 1})} + 1\)で置き換える。

rakeと同様に、compressを行いたいときに各部分木の最大の葉までの深さを \(d_i\) として上記の問題を解き、そのマージ過程で木を作ることが可能です。

そしてこの問題は\(O(M)\) 時間で解くことができます。よって、Static Top Treeの構築も全体で \(O(N \log N)\) ではなく \(O(N)\) 時間で行うことができます。

コアのアイデアは

• \(d_{i - 1} \gt d_i \lt d_{i + 1}\) となっている場合、\(d_i\)を\(1\)増やしてもよい
• \(d_{i - 1} \gt d_i = d_{i + 1}\) となっている場合、\(d_i, d_{i+1}\) をマージしてしまってよい

の2つが言えることです。この証明の本質的なアイデアはhos_lyricさんから頂きました。

この2つの事実により、次のコードの正当性が言えます。このコードは、数列の値を一つ一つstackに追加していき、追加するたびにstackの中身が常に狭義単調減少になるようになるまでmergeしています。このコードは \(O(M)\) 時間で動作するため、構築全体で \(O(N)\) 時間です。

int compress(vector<int> v) {
    assert(v.size());
    vector<int> buffer;
    auto merge = [&]() {
        // bufferの最後の2要素をマージし、マージしたものをbufferにpushする
        int y = buffer.back();
        buffer.pop_back();
        int x = buffer.back();
        buffer.pop_back();
        buffer.push_back(max(x, y) + 1);
    };
    for (int x : v) {
        buffer.push_back(x);
        while (true) {
            int len = buffer.size();
            if (len >= 3 && (buffer[len - 3] == buffer[len - 2] || buffer[len - 3] <= buffer[len - 1])) {
                int z = buffer[len - 1];
                buffer.pop_back();
                merge();
                buffer.push_back(z);
            } else if (len >= 2 && buffer[len - 2] <= buffer[len - 1]) {
                merge();
            } else {
                break;
            }
        }
    }
    while (buffer.size() >= 2) merge();
    return buffer[0];
}

余談

数列の全てのsubstringについて上記の問題を解き、答えの総和を出力 -> https://qoj.ac/problem/3549

HL分解の戦略

最後に、上記のrake / compress戦略を採用した場合の、最適なHL分解を求めるアルゴリズムについて述べます。

これらを総合することで、(高さのmaxのminという意味で)最適なStatic top treeが得られます。

まず、compress戦略についてもう少し考えます。先述の戦略は「stackの中身を常に狭義単調減少になるように管理する」という戦略でした。

ここで、狭義単調な非負整数列 \(d_1 \gt d_2 \gt ... \gt d_k \ge 0\) と非負整数 \(\sum 2^{d_i}\) の間に全単射が存在することを考えると、「stackの末尾に新しい要素を追加し、狭義単調減少になるまでmergeする」、という操作は、あるpair(stackを表す非負整数, 新たに追加する非負整数)を(操作後のstackを表す非負整数)へと移す関数 \(f(d \in \mathbb{Z _{\ge 0}}, a \in \mathbb{Z _{\ge 0}}) \to \mathbb{Z _{\ge 0}}\) と考えることが出来ます。

実際にこの関数 \(f\) の挙動を解析すると、\(2^a\)の倍数になるように切り上げ、\(2^a\) を足す、という操作であることがわかります。

f(d, a) = ((d + (1 << a) - 1) >> a << a) + (1 << a);

この解析によって、\(s \lt t\) ならば任意の \(a\) について \(f(s, a) \le f(t, a)\) が言えます。この性質を利用することで、以下のような木DPが考えられます。

• dp[u] := 頂点 \(u\) 以下の部分木に対してStatic top treeを構成する。\(u\) を含む Heavy pathに対し先述のcompress 戦略を下から適用したときの、while (buffer.size() >= 2) merge();直前でのstackの状態(に対応する非負整数)の最小値

この木DPはbit演算を利用することで全体 \(O(N)\) で計算することが可能です。「子を一つ削除したときのrake戦略の答え」は\(\sum 2^{d_i}\) から容易に計算可能なことに注意してください。

全体的な流れがかなりこの問題に近いため、先にリンク先の問題の解説を先に理解するとわかりやすいと思います。

なお、この構築法だとHeavy pathの末端が木の葉とは限らなくなり、今回の問題固有の事情として、少し実装が大変になります。例えば公式解説のadd_edge関数を、Heavy pathの末端が木の葉ならば return d.b;, そうでないならば return d.a + d.b; とする必要があります。