No.151
釣り堀の右に元の釣り堀を反転させた仮想釣り堀を追加した考える. そして区間 \([0, N)\) には左向きの魚が, 区間 \([N, 2N)\) には右向きの魚がいるとする. こうすることですべての魚は左に動くと考えることができる.
当然ながら左端まできた魚は右端に移動すると考える. すなわち, 位置については \(2N\) で割った余りで考えることになる.
時刻 \(0\) で \(y\) にいた魚は時刻 \(t\) では \(y-t\) に移動している. 逆に時刻 \(t\) で \(y\) に投入された魚は時刻 \(0\) で \(y+t\) に投入されたと考えてもいい. 同様に時刻 \(t\) で区間 \([y, z)\) の魚の数を数えるということは, 時刻 \(0\) で区間 \([y+t, z+t)\) の魚の数を数えることになる.
以上の考察をもとに \(2N\) の長さの釣り堀を Fenwick Tree で管理する.