この解法はクエリの内容を先読みする、というものであった。オフラインアルゴリズムである。これを計算量をキープしつつオンラインにする方法を2つ紹介する。1で用いたデータ構造を永続化することにより、クエリにオンラインで答えることができる。操作の履歴データを持つ。履歴から取り出し、それに対して区間クエリを実行、答えを得る。オフラインならば上図の赤いタイミングでクエリを処理できたが、今回は位置が分からないので・・・このように、それぞれの対象区間を処理したタイミングでのデータ構造を持っておけば、後でどこにクエリが来ても正しく答えが出る。