Segment Tree Beats

# Segment Tree Beats https://codeforces.com/blog/entry/57319 を雑に訳したメモ ## 何ができるの？ 1. 区間[l,r)にchmin/chmaxする操作を区間加算、区間減算にO(logN)かO(1)で変換する 2. history max/min/sum query を区間chmin/chmax にO(1)で変換する ### 解ける問題の例以下の入力が与えられるものとする要素数$N$の配列$A$ 補助用の配列として$A$と同じ状態で初期化された$B$、全て0で初期化された$C$ #### Task1 : 2種類のクエリに答えろ 1. $i \in [l,r]$について$\text{chmax}(A_i, x)$ 2. $\sum_{i=l}^r A_i$を出力する $O(n\log{n})$で解ける #### Task2 : Task1にクエリを追加 1. $i \in [l,r]$について$\text{chmax}(A_i, x)$ 2. $i \in [l,r]$について$\text{chmin}(A_i, x)$ 3. $i \in [l,r]$について$A_i += x$ 4. $\sum_{i=l}^r A_i$を出力する $O(n\log^2n)$で解けるちゃんと証明してないけどもしかしたら$O(n\log{n})$のままかも #### Task3 : 別のものを出力させる 1. $i \in [l,r]$について$\text{chmax}(A_i, x)$ 2. $i \in [l,r]$について$\text{chmin}(A_i, x)$ 3. $i \in [l,r]$について$A_i += x$ 4. $\sum_{i=l}^r B_i$を出力する操作で$A_i$が変化したら$B_i += 1$ 計算量はTask2と同じ #### Task4 : 複数の配列について扱う $A_1, A_2$は長さ$n$の配列 1. $i \in [l,r]$について$\text{chmin}(A_{a,i}, x)$ 2. $i \in [l,r]$について$A_{a,i} += x$ 3. $i \in [l,r]$について$\text{max}(A_{1,i} + A_{2,i})$を出力する $O(n\log^2n)$で解ける配列が$K$個だったら$O(n2^k\log^2n)$ #### Task5 : historicな情報のクエリ 1. $i \in [l,r]$について$A_{a,i} += x$ 2. $\sum_{i=l}^r B_i$を出力 3. $\sum_{i=l}^r C_i$を出力各操作ごとに$\text{chmax}(B_i, A_i), C_i += A_i$と処理 $B$については$O(n\log^2n)$、$C$については$O(nlogn)$で解ける #### Task6 : いろいろ混ぜてもできる 1. $i \in [l,r]$について$\text{chmax}(A_i, x)$ 2. $i \in [l,r]$について$A_i += x$ 3. $\sum_{i=l}^r B_i$を出力する各操作ごとに$\text{chmin}(B_i, A_i)$ ## 主要なアイデア ### 区間chmin/chmax セグ木の拡張版のテンプレートを紹介するね！下のコードはよくある遅延セグ木のupdate関数 ```cpp void modify(int node, int l, int r, int ll, int rr) { if (l > rr || r < ll) return; if (l >= ll && r <= rr) { puttag(node); return; } pushdown(node); int mid = (l + r) >> 1; modify(node * 2, l, mid, ll, rr); modify(node * 2 + 1, mid + 1, r, ll ,rr); update(); } ``` 重要なのはできるときにreturn、puttagをすること区間が交差していない　→　即座にreturn可能区間が内包　　　　　　→　puttagをすればよいこの条件を自由に置き換えることで拡張が可能 ```cpp void modify(int node, int l, int r, int ll, int rr) { if (break_condition()) return; if (tag_condition()) { puttag(node); return; } pushdown(node); int mid = (l + r) >> 1; modify(node * 2, l, mid, ll, rr); modify(node * 2 + 1, mid + 1, r, ll ,rr); update(); } ``` 難しいデータ構造の問題では l>=ll && r <= rr のような弱い条件でputtagを行うのは不可能 tag_condition()に強い条件を入れることで処理できる問題が存在する(計算量解析には注意！) **Simple task** 1. $i \in [l,r]$について$A_i %= x$ 2. $i \in [l,r]$について$A_i = x$ 3. $\sum_{i=l}^r A_i$を出力ちょっとシンプルな問題のジャッジ → [D. The Child and Sequence](https://codeforces.com/contest/438/problem/D) 想定解は平衡二分探索木でA_iが同じ区間を管理するクエリ2は$A_i>=x$の区間を探して値を変える(ここよくわからない) セグ木でもこれは解けて break_condition を l>rr || r<ll || max_value[node] < x とし tag_condition を l>=ll && r <= rr && max_value[node] == min_value[node] とすればok 計算量は$O(n\log^2n)$ [コード](https://codeforces.com/contest/438/submission/50549308) **メインアイデア** 各頂点についてmax_value[node]=(最大の値)とsecond_value[node]=(厳密に2番目に大きな値)を管理する。$\text{chmin}(A,x)$の操作をするとき break_condition を l>rr || r<ll || max_value[node]<=x とし tag_condition を l>=ll && r<=rr && second_value[node] < x とすればよい。この条件の元でputtagをした場合max_valueがxに変更される。何問か解いてみる **Task1** maxとsecondに加えてcnt[node] = (頂点が対応する区間でmaxと等しい要素の個数) を持つ。chminで値が変化した場合 cnt[node] * (maxの変化量)をsum[node]に加えるとすればよい。 https://ideone.com/ysEgXx chmaxがchminになってたけど実質同じなのでまあ **Task2** max, maxのsecond, maxのcnt, min, minのsecond, minのcnt, sum 区間chmin、区間chmax、区間add用のlazy　3種類 chmin → maxが変化、sum += maxのcnt $\times$ (maxの変化量)、min・minのsecondが変化するなら変える chmax → minが変化、sum += minのcnt $\times$ (minの変化量)、max・maxのsecondが変化するなら変える add → max,min,maxのsecond,minのsecond全部プラス sumは区間長を掛けてプラス ToDo: 実装 chminでminとかが変わりうるのが大変そうに見える ### Historic information 以下の3つの値をhistoric informationと呼ぶことにする 1. historic maximum value : 各操作ごとに$\text{chmax}(B_i, A_i)$ 2. historic minimum value : 各操作ごとに$\text{chmin}(B_i, A_i)$ 3. historic sum : 各操作ごとに$C_i += A_i$ 中国ではこの値を聞くデータ構造ゲーが既出らしい Task5のような区間加算/減算とhistoric informationの区間和が飛んでくる問題を考える普通の遅延評価テクニックではこれを解くのは非常に難しい補助配列として$D_i$を使う初期時点では$D_i=0$となっている 1. Historic maximum value : $D_i=B_i-A_i$とおく $A_i += x$をするとき$D_i=\text{max}(D_i-x,0)$とする 2. Historic minimum value : $D_i=B_i-A_i$とおく $A_i += x$をするとき$D_i=\text{min}(D_i-x,0)$とする 3. Historic sum : $D_i = C_i-tA_i$とおく tは操作が何番目かを表す $A_i+=x$をするとき$D_i -= (t-1)x$ chmin/chmaxは上記のテクで扱えるので$D_i$の区間和についての管理はできるよって$B_i, C_i$の区間和についても取得できる ## 計算量解析元のブログが読めないのでこれを読んだ http://codingwithrajarshi.blogspot.com/2018/03/segment-tree-beats-complexity.html 通常のセグメントツリーでは$O(\log{N})$個の区間しか見ないので問題ないことが保証される。しかしbeatsではtag_conditionの条件がより厳しいものになっているので見る区間が増えている。この場合でも計算量が問題ないことを証明する。 ### 基本的な概念タグという概念を定義する。タグは頂点が表す区間の最大値である。親の頂点の最大値と一致する場合その頂点にタグは存在しないものとする。 ※注意：このタグは最初のこどふぉの記事で遅延評価用に使っているlazy tagとは全くの別物であることに注意！これ以降タグと言ったら最大値のことを示すタグの説明はこどふぉのブログの図がわかりやすい以下の3点が重要な性質である * 最大値がタグである * 先祖が同じ最大値を持っている場合その頂点はタグを持たない * second_max = 子孫の頂点のタグの最大値となる二番目の性質は特に重要であるセグメント木の頂点はordinary nodesとextra nodesの2種類に分類できる。ordinary nodesは普通のセグ木の探索で参照する頂点のことでextra nodesはbeatsでtag conditionを変えたことで追加で参照するようになった頂点のことである。beatsでの総計算量はO((ordinary nodesの分のNlogN) + (extra nodesに訪れる回数))となる。 ### Task1 区間chmin区間和の問題　N要素、Nクエリとする $\Phi(X)=\sum_{\text{頂点}v} (\text{子孫に存在するuniqueなタグの個数})$とする。ここでuniqueとは同じ更新の際につけられたタグは同じものとして重複カウントしないということである。セグメント木には高々$N$個しか存在しない。また各タグの先祖になりうる頂点は高々$\log{N}$個であるから$\Phi(X)$の初期値は$O(N\log{N})$である。ポテンシャル関数の変化について観察しよう。 * タグが新たに追加されうるのはordinary nodesだけでありこれは$O(\log{N})$個しか存在しない。また数えるタグの個数はuniqueであるからそれぞれの頂点で高々1しか加算されない。よって区間chminの更新を行うときポテンシャル関数に加算される値は高々$O(\log{N})$である。 * pushdown()で増加しうるポテンシャル関数$\Phi$は高々2 * extra nodeに訪れると子孫のタグを削除する必要がある。またあるタグが削除されるならば子孫の中の同じタグも全て削除される。よってextra nodeに訪れるとポテンシャル関数が少なくとも1マイナスされる。ここまでをまとめると訪れるextra nodeの数の上界がわかる * $\Phi(X)$の初期値が$O(N\log{N})$で$N$回のクエリで$O(\log{N})$ごと増えることから$\Phi(X)$の値は高々$O(N\log{N})$ * extra nodeに訪れると$\Phi(X)$がマイナスされる * ポテンシャル関数の定義から$\Phi(X) >= 0$ → extra nodeを訪れる回数はクエリ$N$回合計で$O(N\log{N})$回 extra node以外に関する計算量は普通のセグ木と同じなので計算量は全体でもamortized $O(N\log{N})$ ### Task2 $\Phi(X)=\sum_{\text{タグ}T} T\text{の深さ}$とする。深さの最大は$O(\log{N})$であるから$\Phi(X)$の初期値は$O(N\log{N})$となる。ポテンシャル関数の変化はどのようになっているか？ * pushdown()ごとにポテンシャル関数に加えられる値は$O(\log{N})$でordinary nodesの数は$O(\log{N})$なのでクエリごとにポテンシャル関数に$O(\log^2N)$加算される * extra nodeにアクセスすると削除する必要があるのでマイナスされる計算量は$O(N\log^2N)$