累積和・差分配列
一次元区間や多次元直方体の情報、または一括加算を接頭辞・端点の差へ変換し、query・数え上げ・復元に使う。
この典型を扱う単元: 一次元・二次元累積和と差分で区間情報を線形化する
検索別名: difference array、prefix sums、いもす法、累積和
未知問からこの典型を見つける手掛かり
- 扱う対象
- grid
- prefix
- rectangle
- 区間
- 合計
- 矩形
- 配列
- 使う手掛かり
- 4.*corner
- rectangle.*query
- 一括加算
- 区間和
- 連続区間
- 保つ不変量
- prefixの差
- total.*inside
- 左端と右端
- 差分
- 補集合
- 求めるもの
- distinct
- 区間和
- 各位置の値
- 種類数
- 集計
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
学習成果と学習単位
prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。
一次元・二次元累積和と差分で区間情報を線形化するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC216 G「01Sequence」 公式問題主題: difference constraints・不等式系の最短路化 / 補助タグ
- ABC228 F「Stamp Game」 公式問題主題: 支配関係から不要な候補を単調stack・queueで削る / 補助タグ
- ABC233 Ex「Manhattan Christmas Tree」 公式問題主題: parallel binary search・多数境界の判定共有 / 補助タグ
- ABC233 G「Strongest Takahashi」 公式問題主題: 区間合成・領域分割DP / 補助タグ
- ABC238 E「Range Sums」 公式問題主題: DSUによる連結成分管理・縮約 / 補助タグ
- ABC253 F「Operations on a Matrix」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ
- ABC260 G「Scalene Triangle Area」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 主タグ
- ABC268 E「Chinese Restaurant (Three-Star Version)」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 主タグ
- ABC276 Ex「Construct a Matrix」 公式問題主題: 線形方程式・rank / 補助タグ
- ABC278 E「Grid Filling」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 主タグ
- ABC282 G「Similar Permutation」 公式問題主題: DP遷移を因数分解・集約して加速する / 補助タグ
- ABC298 G「Strawberry War」 公式問題主題: 区間合成・領域分割DP / 補助タグ
- ABC300 F「More Holidays」 公式問題主題: 単調境界を証明して探索する / 補助タグ
- ABC307 G「Approximate Equalization」 公式問題主題: 資源・容量DP / 補助タグ
- ABC311 G「One More Grid Task」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC330 F「Minimize Bounding Square」 公式問題主題: 単調境界を証明して探索する / 補助タグ
- ABC330 G「Inversion Squared」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC333 E「Takahashi Quest」 公式問題主題: 成立証明から構成解を復元する / 補助タグ
- ABC341 E「Alternating String」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 主タグ
- ABC347 F「Non-overlapping Squares」 公式問題主題: 候補数を界して全列挙・有限case分解する / 補助タグ
- ABC404 G「Specified Range Sums」 公式問題主題: difference constraints・不等式系の最短路化 / 補助タグ
- ABC407 F「Sums of Sliding Window Maximum」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: event・値順のオフライン走査、ordered set・multisetの動的順序管理、累積和・差分配列
- ABC410 F「Balanced Rectangles」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 主タグ
- ABC420 F「kirinuki」 公式問題主題: 大小関係をCartesian treeへ変換する / 補助タグ
技能・出典
主タグ: Cartesian treeによる区間極値分解 / 補助タグ: 単調stack・queueによる支配候補の削除、累積和・差分配列
- ABC421 G「Increase to make it Increasing」 公式問題主題: 最小費用流・circulation / 補助タグ
- ABC423 E「Sum of Subarrays」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC427 E「Wind Cleaning」 公式問題主題: 状態グラフのモデリングと探索 / 補助タグ
- ABC430 F「Back and Forth Filling」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 主タグ
- ABC441 E「A > B substring」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 主タグ
- ABC452 E「You WILL Like Sigma Problem」 公式問題主題: 整数境界と同値区間を正確に分ける / 補助タグ
- ABC454 F「Make it Palindrome 2」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 主タグ
- ABC455 E「Unbalanced ABC Substrings」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC465 F「Sjeltzer?」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 主タグ
- ABC465 G「Sum of Mex of Mod of Linear」 公式問題主題: 端点更新型のrun分割管理 / 補助タグ