数列 \(W = (W_1, W_2, \cdots, W_{2^{N+1} - 1})\) を次のように定義します。

\[ W_i = \begin{cases} C_i & (2^N \le i \lt 2^{N+1})\\ \min\{C_i, W_{2i} + W_{2i+1}\} & (1 \le i \lt 2^N) \end{cases} \]

これは、元のグラフのある辺を使う際に、その中央にある頂点を経由した方が安いならそちらを使ったほうがよいという事実を反映した重みです。 \(C\) の代わりに \(W\) における最短路を考えても答えは同じになるので、以降は \(W\) における最短路を考えるものとします。

2 s t のクエリについて考えます。 \(s\) から \(t\) への最短路において、 \(s, t\) 以外で奇数の座標 \(x\) を通ると仮定します。すると、 \(x\) の前後では最下段（タイプ \(N\) ）の辺を使っていますが、それは同じ辺を往復している（無駄）か、連続する辺を使っている（ \(W\) の定義より、代わりに親の辺を使えばよい）かのどちらかであるので、そのような \(x\) は存在しないと仮定してもよいです。

よって、最下段（タイプ \(N\) ）の辺は、 \(s, t\) がそれぞれ奇数のときに最初と最後に用いる分に限ります。このとき、左右どちらに行くべきかは不明であるため、両方のパターンを試すことにします。その後はタイプ \(N-1\) 以下の辺のみを考えることで再帰的に計算ができます。

一見すると再帰が深くなるたびに始点と終点の候補が増えていくように思われますが、「始点の候補は高々 \(2\) つであり、連続する \(2\) 点である」ことが帰納的に確認できます。これは、連続する \(2\) 点があれば、偶数と奇数がそれぞれちょうど \(1\) つずつあることから、奇数の方が次に左右に分岐し、その一方は偶数と合流することから示せます。

したがって、 \(O(N)\) で 2 s t のクエリに答えられます。

1 j x のクエリについて、 \(W\) はデータ構造の Segment Tree のようにして \(O(N)\) で \(C\) の変更に追従できます。ここで、変更される要素は \(W\) ではなく \(C\) の要素であることに注意してください。

以上から、クエリあたり \(O(N)\) で処理できるため、時間計算量 \(O(2^N + QN)\) 、空間計算量 \(O(2^N)\) で問題が解けました。

この解説は noshi91 さんによる証明を改変したものです。