We define the sequence \(W = (W_1, W_2, \cdots, W_{2^{N+1} - 1})\) as follows:

\[ 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} \]

This reflects the fact that, if it is prefer to pass through the intermediate vertex instead of using a certain edge, then we should do so.

Since considering the shortest path in \(W\) yields the same result as in \(C\), we will focus on finding the shortest path in \(W\) from now on.

We consider a query 2 s t. Suppose in the shortest path from \(s\) to \(t\), here exists an coordinate \(x\) with odd number other than \(s, t\) through which the path passes. In this case, the path would either traverse the bottom layer edges (type \(N\) ) back and forth over the same edge (which is inefficient), or use consecutive edges (by the definition of \(W\), we can use their parent edge instead). Therefore, we can assume such \(x\) does not exist.

Thus, edges in the bottom layer edges (type \(N\) ) are used only at the beginning or end of the path when \(s\) and \(t\) are odd respectively. In this case, it is uncertain whether to go left or right, so we will try both options. After that, we can recursively compute the path by considering only edges of type \(0, 1, \cdots, N-1\).

At first glance, it may seem that the number of potential starting and ending points increases as recursion deepens. However, we can confirm inductively that “there are at most \(2\) candidate starting points, and it will be consecutive points”. This is because, given \(2\) consecutive points, then one will be even and the other odd. The odd one will branch to the left or right next, then one of these branches will merge back with the even point, thereby we can prove that.

Therefore, we can answer to a query 2 s t in \(O(N)\) time.

For a query 1 j x, \(W\) can follow changes to \(C\) in \(O(N)\) time, similarly to a segment tree (as a data structure). Note that modified elements are of \(C\), not those of \(W\).

Finally, each query can be processed in \(O(N)\) time, allowing the problem to be solved with a time complexity of \(O(2^N + QN)\) and a space complexity of \(O(2^N)\).

This explanation is a modified version of a proof by noshi91.