典型タグ

値軸のbucket分割と区間集約

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

この典型を扱う単元: 値軸のbucket分割と区間集約

検索別名: block集約、bucket decomposition、値軸平方根分割

未知問からこの典型を見つける手掛かり

扱う対象
  • block要約
  • 値prefix
使う手掛かり
  • queryより更新が多い
  • 定数時間の点更新
保つ不変量
  • 値別頻度の集約
  • 完全blockと端数
求めるもの
  • 更新queryの計算量配分
  • 頻度和と積
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: 更新可能な最小十分要約

    関連する典型

    学習成果と学習単位

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

      値軸のbucket分割と区間集約で学ぶ

    代表問題

    この典型の考え方を具体的な問題で確かめるための入口です。

    関連問題

    この典型が主タグまたは補助タグとして付いている問題です。