葉は左から順に値$[1,2^N]$が振ってある。以下のクエリを順次処理せよ。左から$a$番目の頂点(葉)の値を答える。bfs順で$[a,b]$番目の頂点(葉ではない)の左右の部分木を入れ換える。$a$番目の頂点に関して入れ換え、その後の状態における$a+1$番目の頂点に関して入れ換え、という風にやる。完全二分木の高さ$N+1$に対し$O(QN^2)$。愚直に実装するとすると、木を作製し実際に参照をswapすればよい。それではもちろん間に合わないので、参照を操作するのではなく、swap済みflagをtoggleすることを考える。するとこの操作は$0,1$の区間に関するxorのようなものになるので、segment木が視野に入ることになる。葉の参照のクエリは、左の部分木と右の部分木のどちらに降りるかを、$a-1$の$i$-bit目とswap済みflagのxorで決めながら降りていき、辿り付いた葉の位置が答えるべき値である。木の更新であるが、更新処理それ自体もswap済みflagの影響を受ける。2$のswapのクエリが来たとする。3$の頂点をswapせねばならない。このswap済みflagの処理を、segment木を使って高速に処理する。ある程度の区間をまとめて処理することが目的であるので、深さ$k$の部分木らのswap済みflagsに関して$1$本のsegment木を用意する。2^N$個である$N+1$本のsegment木を用いる。これらの上に、swap済みflagを考慮した上での区間更新演算を実装すればよい。それぞれのsegment木の区間の要素は$1$bitであるので、$N+1$bitの整数にまとめれば$1$本のsegment木で同じ処理を行うことができる。