根を0段目とする.

シフトは数値に対して行われるが, 同じ段のどの数値に対してシフトを行っても結果は同じなので, どの段かさえ分かればいい.

\(i\) 段目に適用された右シフト量を値シフト, ノードシフトごとに記録しておく. この値を \(v_i\), \(n_i\) とする. \(2^i\) 以上のシフトは元に戻るので \(2^i\) の余りだけ持っておけばいい. 左シフトは \(2^i\) を足して右シフトに変換する.

こうすることで, \(i\) 段目のシフト量 \(s_i\) は以下のように求められる.

\[N_i = \sum_{j=1}^i 2^{i-j}n_i \\ s_i = v_i + N_i\]

なお, 上位ノードのシフト量を求める必要もあるので, \(N_i = 2N_{i-1} + n_i\) を利用してメモしておく.