反転数・重み付き接頭辞統計をFenwick Treeで保つ

概要

Fenwick Tree・反転数・重み付き接頭辞統計

値や座標の頻度を動的な接頭辞和で数えて反転数を求めるか、複数本を組み合わせて次数付きの区間式を評価する。

ABC296 Fでは、二列のmultisetが一致し、値がすべて異なる場合に反転数の偶奇を比較する。左から値を追加し、既出個数から現在値以下のprefix頻度を引けば新たな反転数が得られる。重複がある場合に置換の偶奇を調整できるという証明と、その不変量を計算するFenwick treeの役割を分ける。

考え方

Fenwick Treeの節点に末尾bitで決まる区間の集計値を置く。prefixを互いに素なO(log N)区間へ分解し、点更新の影響もO(log N)節点へ伝播する。

lowbit区間・初期化・更新

1-indexで lowbit(i)=i & (−i) とし、bit[i]にa[i−lowbit(i)+1,…,i]の和を置く。全0から始め、点pへΔを加えるならi=pから bit[i]+=Δ; i+=lowbit(i) をi≤Nの間繰り返す。prefix [1,r]はans=0,i=rから ans+=bit[i]; i-=lowbit(i) をi>0の間繰り返す。queryで取る区間は重複せずprefixを覆い、更新で訪れる区間は点pを含む全担当区間である。

反転数を数える場合は値を圧縮し、左から読む。既にi個処理して現在値の順位がpなら、頻度BITのprefix(p)は現在値以下の個数なので、現在の反転寄与は i−prefix(p)。query後に点pへ1を足す。同値を反転へ含めないため≤を引く。

重み付き統計は求める式を先に分離する。例えば既出a_j≤xの Σ(x−a_j) は x·count(≤x)−sum(≤x) なので、個数と値の和の二本のBITで得られる。区間加算・区間和なら差分d_jを持ち、prefixの和は Σ_{i=1}^r a_i=(r+1)Σ_{j≤r}d_j−Σ_{j≤r}j d_j。区間[l,r]へΔを加えるとd_l+=Δ、d_{r+1}−=Δだけなので、d_jとj d_jの二本へ点更新する。

成立条件と計算量

点加算・prefix和はO(log N)、区間和には引き算が必要。個数と値の総和を並べて持てば重み付き統計を求められる。k番目の二分探索はprefix個数が単調となる非負頻度が前提。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。座標圧縮と動的prefix和を組み合わせ、反転数や重み付き統計を数える。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-weighted-prefix-fenwick

習得する技能

  • 処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。

前提と範囲

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

直接の前提単元: 一次元・二次元累積和と差分で区間情報を線形化する。

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

静的な接頭辞差分を理解した後、点更新を伴う頻度・反転数・重み付き接頭辞統計をFenwick Treeで保つ。

このUnitでは扱わないもの

  • 一般のモノイドによるSegment Treeの区間要約。

根拠