メモ

yukicoderでゆるふわgolf

segment tree beats 覚書

これを読め
rsm9.hatenablog.com
~終わり~


以下ポエム
ひとなのでさんによるこの記事を読むまでbeatsの理解が困難だったが、この記事を読むと全てを3秒で理解できた。
これ以前に存在していた記事で理解が困難だったのは、まずそもそもbeatsというデータ構造の概念の部分の話・実装に関する話・計算量解析に関する話がいっしょくたにされていることが多かったため。
beatsの本質は「mapping(f,x)が計算できないなら、op(left,right)で計算する」というだけ。冒頭の記事ではこれを一番最初に説明してくれており、それでようやくbeatsというものが何をするデータ構造なのか理解できた。この段階では計算量解析には触れずに「もしそういうことができるなら、これでうまくいくね」という話し方をしている。非常にわかりやすい。

作用 f(x) の計算に失敗してしまった場合,「とりあえず f を x の子に伝播させて子の計算を先に行い,子に関する計算結果を用いてボトムアップに x′ を再構築する」という方法で問題を回避できそうです.ここで計算の失敗回数が多すぎる(例えば列の長さ N やクエリ個数 Q に関する二乗のオーダーになってしまう)と計算量が悪化してしまいますが, S や F の構造などに由来する何らかの理由で「Segtree 上の全頂点における失敗回数の合計」に良い上界(例えば O((N+Q)log2⁡N))が与えられるならば,計算量の本質的な悪化が回避でき,高速なクエリ処理が可能となります.

atcoder::lazy_segtree に1行書き足すだけの抽象化 Segment Tree Beats - ひとなので

実装パートも、beatsが何なのかを冒頭のように理解していれば1行書き足すだけなのは自明。非常にわかりやすい。
計算量解析パートの理解が困難だったのも、chmin/sumのような複雑な例を最初に出されることが多かったため。ひとなのでさんの記事はこの点でも完璧で、1番目の例は、gcdが本質的にchminであることから「failするたびその区間に属する値の"max"が真に小さくなるため(特に1回目でクエリの値まで落ちる)」と簡単に理解できる。次の例も「(Z/2Z)^64という束の"高さ"が64であり、failするたびにその区間に属する値の"min"と"max"の"高さ"の差が真に小さくなるため」と理解できる(ハッセダイアグラムを頭に思い浮かべながらchand/chorクエリの効果をイメージできますか?ぼくはできます)。わかりやすい。
データの持ち方パートについても、これらはともに「chminがうまく走るか見たいから区間の最大値もっとこ(最大値<chminクエリの値なら無視できるので)」というだけなのでかなり自然。
それに比べてchmin/sumはめちゃくちゃ複雑。なぜかというと「failするたびにその区間に属する値のmaxが真に小さくなる」を言っても、それは1e9回起こりうるため。もっと小さくなる何かを持ちてえなあという気持ちになり、second maxを持って区間内の値の種類数を減らそうと思える(は?)。計算量解析は難しい(「failするたびにその区間に属する値の種類数が減るため」ではO(N^2)しか言えないので)(は?) こんなもんを初心者に見せるな
以上です。