値軸のbucket分割と区間集約

概要

値軸を長さBのblockに分け、完全blockの要約と端数の走査を合成する。点更新とqueryの回数を別々に数え、O(1)更新とO(V/B+B)の値prefix取得を選ぶ。

値域を0,…,V−1、block幅をBとし、block jは[jB,min((j+1)B,V))とする。和の要約S_j=Σ a_vは初め配列から構築し、全て0の配列ならS_j=0。一点a_vをoldからnewへ変えるとき、j=floor(v/B)としてS_j←S_j+new−old、a_v←newとする。

半開prefix[0,x)の取得ではq=floor(x/B)を求め、全S_j(j<q)と、残りのa_v(qB≤v<x)を足す。x=Vがblock境界なら端数は空であり、x=0の答えは0。各位置は完全blockか端数の一方にただ一度含まれるので正しい。一般の結合演算でも同じ分割でqueryできるが、旧寄与を取り消す操作がなければO(1)更新はできない。

積の要約P_j=∏ a_vは、可逆な旧因子ならP_j←P_j·old^(−1)·newと直せる。ただし逆元を一回O(log p)の累乗で求める実装はO(1)更新ではなく、逆元が前計算済みか、更新時に定数回の演算で得られる場合に限りO(1)となる。0や非可逆因子にはこの除去式を適用しない。素数法で0を扱う場合は、非零因子の積と0の個数を別々に持つ方法を動的mod積で学ぶ。

ABC405 Gはこの更新と取得の非対称性をMoに組み込む。各値の頻度とblock内のΣf_v、∏invFact[f_v]を持ち、値の重複数に依存する並べ替え数を計算する。頻出値をheavyへ分類する方法とは、分割対象も計算量の証明も異なる。

この例ではf_v=0、和0、積1から始め、最大頻度が素数法p未満となるようfactorialとその逆元を前計算する。f→f+1では和へ1、積へinv(f+1)を掛け、f→f−1では和から1、積へfを掛ける。invFact[f+1]/invFact[f]=1/(f+1)からこの定数時間更新が従う。prefix内の頻度和をn、その逆階乗積をPとすれば、同じ値を区別しない並べ替え数はn!·P。位置を動かすMoの費用と、この値prefix取得の費用を分けて数える。

考え方

値域をbucketへ分け、各bucketの個数や和を持つ。prefixは丸ごとのbucketと端の部分走査へ分けられ、複雑な木を使わず更新と集計を釣り合わせられる。

成立条件と計算量

和の初期構築O(V)、U点更新とQ prefix取得ならO(V+U+Q(V/B+B))時間、O(V)空間。queryがある単純なこのモデルではB≈√Vで二項を釣り合わせる。block全体の再構築が要る更新ならUの係数にもBが現れるため、実際の更新・query回数から総費用を作り直す。疎な値域は座標圧縮し、順位と実値の総和を区別する。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。平方根分割で完全blockと端数を分け、更新とqueryの費用を調整する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-value-bucket-aggregation

値軸のbucket分割と区間集約

習得する技能

  • 値軸をblockへ分け、点更新で要約を差分修正し、完全blockと端数からprefixの和・積を取得できる。更新回数とquery回数に応じてblock幅を選べる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

値軸を長さBのblockに分け、完全blockの要約と端数の走査を合成する。点更新とqueryの回数を別々に数え、O(1)更新とO(V/B+B)の値prefix取得を選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • 値軸のbucket分割と区間集約の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠