Segment Tree Beatsの計算量解析
ferinさんのSegment Tree Beatsの解説（計算量解析の部分を参照）
とyaketake08さんのSegment Tree Beatsの解説（Segment Tree Beatsの動作を参照）
を元にSegment Tree Beatsの計算量を解析する。
タグ（後ろで説明）の取り方や解析方法を微妙に元記事（ferinさん）と変えている。
問題１
数列$ a_1,a_2,\ldots,a_nに対して
クエリ１
$ i\in \lbrack l, r) に対して$ a_i \leftarrow \min(a_i,m)
（$ l,r,mはクエリ毎に異なってよい）
クエリ２
$ \sum_{i=l}^{r-1} a_i
（$ l,rはクエリ毎に異なってよい）
の二つのクエリを処理せよ。
Segment Tree Beatsでクエリ毎に$ O(\log n)で処理できる。
計算量解析
セグメント木の各頂点$ vに対応する範囲の数列の項の最大値、二番目に大きい値を
$ first(v),second(v)と置く。葉$ vは項が一つしかないが$ second(v)=-\inftyとする。
また、頂点$ vの左子、右子を$ v.left,v.rightと置く。
仮想的に全ての遅延している作用素を葉まで伝搬させ切ったとする（この点はferinさんの記事と異なる）。
この時、各頂点vについて親とfirstの値が違うとき、その頂点に値first(v)のタグを付与する。
ordinary node、extra nodeの定義はferinさんの解説を参照せよ。
クエリ2はordinary nodeを走査するだけであるから通常のセグメント木と同様にクエリ当たりの計算量は$ O(\log n)である。
従ってここではクエリ1の計算量を解析する。
定理 1.1
extra nodeである頂点vに到達した際、second(v)≧mならばv.left, v.rightに移動する。
この際、vの子孫であって値v.secondのタグは全て失われる。
証明
各頂点を〇、頂点に対応する区間の数列の最大値を〇の中に書き込んで表す。
頂点uについてfirst(u)=aだとする。このとき、子の一方はfirstがaになる。
$ first(u.left)=a, first(u.right)= b, a\geq bだとする（右子、左子の値を入れ替えたものも同様に考えればよい）。
更新前の図
https://gyazo.com/593feb604023b5798befdc1974411782
頂点uがextra nodeだった場合、uの表す数列の範囲は完全にクエリの更新範囲に含まれるため、m,a,bの大小関係に応じて更新後は次の3つの関係のいずれかになる。
extra nodeの更新後の図
https://gyazo.com/b7f9a38e6e054970e1019479ffbfc916
更新前に頂点uの子であって値second(v)のタグである頂点が存在しているとする。
それは頂点uの右子、つまりb=second(v)でしかあり得ない。second(v)≧mだから更新後は(iii)の通り、first(u)=first(u.left)=first(u.right)=mとなる。従って値second(v)のタグはなくなる。
証明終了。
定理 1.2
タグが新たに追加されるのはordinary nodeだけである。また追加されるタグの値はmのみである。
証明
頂点uの子がextra nodeだった場合、uの表す数列の範囲は完全にクエリの更新範囲に含まれるため、m,a,bの大小関係に応じて更新後は次の3つの関係のいずれかになる。
https://gyazo.com/d1473707dd3cb6fcfc0e592a9f0766a7
いずれの場合もuの子に対して新たに追加されるタグはない。従ってextra nodeには新たなタグは追加されない。
ordinaly nodeでは更新後、上の三つの図以外に次の図の関係があり得る。この時、頂点uの右子のタグの値はbからmになる。
ordinarly nodeの更新後の一例の図
https://gyazo.com/cc722a9c2bb50e6c1bcc2ed84e5f8bc5
証明終了。
ポテンシャル関数の定義
ポテンシャル関数$ \Phiを
$ f(v):=($ vの子孫のタグの値の種類数)
$ \Phi:=\sum_v f(v)
のように定義する。
定義から$ \Phi\geq0である。
仮想的に全ての遅延している作用素を葉まで伝搬させ切ったとする。
このとき、セグメント木の葉の種類数は$ O(n)である。
各葉から親の方へタグのついている頂点に到達するまで繰り返し移動する。
このようにして到達できるタグ付きの頂点で全てのタグ付きの頂点が尽くされる。
タグ付きの頂点の子孫の数はそれぞれ$ O(\log{n})個である。
従って$ \Phiの値は常に$ O(n\log n)である（＊）。
定理2よりクエリ1においてタグはordinary nodeにしか追加されず、タグの値は全て$ mである。
このとき、ordinary nodeである頂点$ vでしか$ f(v)の値は増加しない。また値$ mのタグが追加されただけであるから増加量は高々1である。ordinary nodeの数は$ O(\log{n})よりクエリ毎の$ \Phiの増加量も$ O(\log n)である。
以上から、
$ \Phi-\Phi_{\mathrm{initial}}= O(Q \log n) -O(\sum_{クエリ1毎の和}(ordinary node と extra nodeからなる木からordinary nodeと葉を除いた頂点数)$ )
$ \Rightarrow O(n\log n)=O(Q \log n) -O(\sum_{クエリ1毎の和} extra nodeの数$ )
となる。
ここで$ \Phi_{\mathrm{initial}}はセグメント木の初期状態における$ \Phiの値、$ Qはクエリ1のクエリ数である。
$ Q=n とすると、$ O(n\log n) = $ O(\sum_{クエリ1毎の和} extra nodeの数$ ) であるから、一クエリに対してextra nodeの数は均し$ O(\log n)である。
クエリ当たりの計算量はO(ordinary nodeの数) + O(extra nodeの数)であるからクエリ1の計算量は均し$ O(\log n)である。
問題2
数列$ a_1,a_2,\ldots,a_nに対して
クエリ１
$ i\in \lbrack l, r) に対して$ a_i \leftarrow \min(a_i,m)
（$ l,r,mはクエリ毎に異なってよい）
クエリ２
$ i\in \lbrack l, r) に対して$ a_i \leftarrow a_i+M
（$ l,r,Mはクエリ毎に異なってよい）
クエリ３
$ \sum_{i=l}^{r-1} a_i
（$ l,rはクエリ毎に異なってよい）
の３つのクエリを処理せよ。
Segment Tree Beatsで
クエリ１, 2 均しで$ O(\log^2 n)で処理できる。
クエリ２毎に$ O(\log n)で処理できる。
クエリ３毎に$ O(\log n)で処理できる。
クエリ２、３で訪れるのはordinary nodeだけであるから計算量は$ O(\log n)になる。従ってここではクエリ１の計算量を解析する。
ポテンシャル関数$ \Phiを
$ f(v):=(全ての遅延している作用素を葉まで伝搬させ切ったときの$ vの子孫のタグの数)
$ \Phi:=\sum_v f(v)
のように定義する。$ f,\Phiの定義は問題１と異なることに注意せよ。
定理2.1
クエリ２について、$ \Phiの増加量は高々$ O(\log^2(n))である。
証明
ordinary nodeからなる木の葉とextra nodeとextra nodeの子孫は頂点の表す区間が完全にクエリの更新範囲に含まれる。従ってこれらの頂点では対応する数列の項が全て$ M増加し、タグの数は変わらない。
従ってordinary nodeにしかタグは追加されない。ordinary nodeは$ O(\log n)個あり、そのすべてにタグが追加されたとしても$ \Phiは合計$ O(\log ^2 n)しか増加しない。
証明終了。
クエリ１について定理1.2からタグが追加されるのはordinary nodeのみである。
ordinary nodeは$ O(\log N)個あり、そのすべてにタグが追加されたとしても合計$ O(\log ^2 n)しか$ \Phiの増加に寄与しない（これは嘘）。定理1.1から少なくともextra node一つにつき$ \Phiは1減少する。
$ \Phi-\Phi_{\mathrm{initial}} = クエリ１の変化量の合計＋クエリ２の変化量の合計
であるが、定理2.1からクエリ２の変化量の合計＝$ O(Q\log^2 n)である。$ Qはクエリ数である。（＊）から常に$ \Phi = O(n \log n)である($ \Phiの定義は問題１と異なるが同様の議論が適用できる）。
従って、クエリ１, 2 の計算量は均し$ O(\log^2 n)になる。