値軸のbucket分割と区間集約
値軸を長さBのblockに分け、完全blockの要約と端数の走査を合成する。点更新とqueryの回数を別々に数え、O(1)更新とO(V/B+B)の値prefix取得を選ぶ。
この典型を扱う単元: 値軸のbucket分割と区間集約
検索別名: block集約、bucket decomposition、値軸平方根分割
未知問からこの典型を見つける手掛かり
- 扱う対象
- block要約
- 値prefix
- 使う手掛かり
- queryより更新が多い
- 定数時間の点更新
- 保つ不変量
- 値別頻度の集約
- 完全blockと端数
- 求めるもの
- 更新queryの計算量配分
- 頻度和と積
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
- Mo's algorithmによるオフライン区間問い合わせ: Moで区間位置を動かし、値軸のbucketで閾値以下の頻度和・積を取得する。ABC405 Gでは多数の端点更新をO(1)に保つことが両者を組み合わせる理由になる。
- 平方根・閾値による軽重分類: 座標軸を連続blockに分けて完全blockと端数を合成する方法と、対象を頻度・次数の大小で分けて重い対象を前計算する方法を区別する。
学習成果と学習単位
値軸をblockへ分け、点更新で要約を差分修正し、完全blockと端数からprefixの和・積を取得できる。更新回数とquery回数に応じてblock幅を選べる。
値軸のbucket分割と区間集約で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC405 G「Range Shuffle Query」 公式問題主題: Moの順序で区間問い合わせの差分を更新する / 補助タグ
技能・出典
主タグ: Mo's algorithmによるオフライン区間問い合わせ / 補助タグ: 組合せ係数・数え上げ、法上の動的積・剰余 0 因子の分離、値軸のbucket分割と区間集約
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC405 G「Range Shuffle Query」 公式問題主題: Moの順序で区間問い合わせの差分を更新する / 補助タグ
技能・出典
主タグ: Mo's algorithmによるオフライン区間問い合わせ / 補助タグ: 組合せ係数・数え上げ、法上の動的積・剰余 0 因子の分離、値軸のbucket分割と区間集約