一次元・二次元累積和と差分で区間情報を線形化する

概要

累積和・差分配列

一次元区間や多次元直方体の情報、または一括加算を接頭辞・端点の差へ変換し、query・数え上げ・復元に使う。

ABC465 Fの添字は{0,…,9}の6軸の直積。各軸を小さい桁値から累積し、queryの上下端を選ぶ64項の包除で直方体和を取る。桁値1は上限2のprefixに含まれるが、二進の1は2の部分マスクではない。Boolean lattice上の部分集合ゼータ変換と更新関係を混同しない。

考え方

prefixの累積値P[i]を持てば、和の区間[l,r)はP[r]−P[l]で得られる。差分表現では区間加算を両端の変更へ写し、最後に累積して値を復元する。

0-indexではP[0]=0、P[i+1]=P[i]+a_iで初期化する。二次元ならP[i+1][j+1]=a[i][j]+P[i][j+1]+P[i+1][j]−P[i][j]。長方形[x1,x2)×[y1,y2)の和は P[x2][y2]−P[x1][y2]−P[x2][y1]+P[x1][y1] となる。各要素の係数が領域内だけ1、外で0になることが包除の根拠である。

一括区間加算は差分D[l]+=v,D[r]−=vとし、最後にprefixで復元する。二次元の一括長方形加算なら左上と右下に+v、右上と左下に−vを置き、両軸で累積する。D軸の直方体は各隅を、上端を選んだ軸数の偶奇による符号で更新し、2^D隅を使う。

成立条件と計算量

静的前処理O(N)、query O(1)。prefix差を取るには逆演算が必要で、最小値には使えない。二次元では包除の符号を確認する。更新のたび全prefixを書き換えるならO(N)なので、動的には別構造を選ぶ。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 茶色(400–799)。加算と差分で区間を表し、一次元から二次元の包除へ広げる。

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

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

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

習得する技能

  • prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: 反転数・重み付き接頭辞統計をFenwick Treeで保つ。

一次元累積和を土台に、包除で矩形和へ拡張し、静的区間量を接頭辞や端点の差へ変換する。

このUnitでは扱わないもの

  • オンライン更新を伴うFenwick Tree・Segment Treeの動的区間要約。

根拠