Fenwick Tree・反転数・重み付き接頭辞統計
値や座標の頻度を動的な接頭辞和で数えて反転数を求めるか、複数本を組み合わせて次数付きの区間式を評価する。
この典型を扱う単元: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
検索別名: BIT、Binary Indexed Tree、フェニック木
未知問からこの典型を見つける手掛かり
- 扱う対象
- prefix
- 反転数
- 添字付き和
- 配列
- 重み
- 頻度
- 使う手掛かり
- point update
- 一点更新
- 左側に大きい値
- 接頭辞和
- 累積和
- 保つ不変量
- bit
- 係数
- 処理済み頻度
- 複数本の
- 求めるもの
- query
- 動的和
- 区間式
- 反転数
- 適用しない条件
- bit.?dp
- bit.?mask
- bitset
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
- 座標・値の順序保存圧縮: 疎な値を順序保存圧縮してから、個数・重み・反転数をprefix集約する構成で併用する。
学習成果と学習単位
処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。
反転数・重み付き接頭辞統計をFenwick Treeで保つで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC221 E「LEQ」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 主タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 寄与の数え上げと順序交換、座標・値の順序保存圧縮、法上の四則演算・高速累乗・逆元
- ABC256 F「Cumulative Cumulative Cumulative Sum」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 主タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC287 G「Balance Update Query」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC221 E「LEQ」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 主タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 寄与の数え上げと順序交換、座標・値の順序保存圧縮、法上の四則演算・高速累乗・逆元
- ABC231 F「Jealous Two」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC233 Ex「Manhattan Christmas Tree」 公式問題主題: parallel binary search・多数境界の判定共有 / 補助タグ
- ABC253 F「Operations on a Matrix」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ
- ABC256 F「Cumulative Cumulative Cumulative Sum」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 主タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 組合せ係数・数え上げ、法上の四則演算・高速累乗・逆元
- ABC261 F「Sorting Color Balls」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC263 Ex「Intersection 2」 公式問題主題: 単調境界を証明して探索する / 補助タグ
技能・出典
主題: 単調境界を証明して探索する
主タグ: 単調境界探索 / 補助タグ: 円環順序・chord交差、event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計、幾何の基本判定・配置・座標変換
- ABC276 F「Double Chance」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 主タグ
- ABC287 G「Balance Update Query」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 主タグ
- ABC294 G「Distance Queries on a Tree」 公式問題主題: Euler順による部分木区間化 / 補助タグ
- ABC296 F「Simultaneous Swap」 公式問題主題: 同値な状態を正規化する / 補助タグ
- ABC306 F「Merge Sets」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: 座標・値の順序保存圧縮、event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計
- ABC337 G「Tree Inversion」 公式問題主題: Euler順による部分木区間化 / 補助タグ
- ABC341 E「Alternating String」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 補助タグ
- ABC351 F「Double Sum」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 主タグ
技能・出典
主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ
主タグ: Fenwick Tree・反転数・重み付き接頭辞統計 / 補助タグ: 座標・値の順序保存圧縮、event・値順のオフライン走査
- ABC368 G「Add and Multiply Queries」 公式問題主題: 単調進行による償却解析 / 補助タグ
- ABC378 E「Mod Sigma Problem」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC380 G「Another Shuffle Window」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計、法上の四則演算・高速累乗・逆元、尺取り法・sliding window
- ABC384 G「Abs Sum」 公式問題主題: Moの順序で区間問い合わせの差分を更新する / 補助タグ
技能・出典
主タグ: Mo's algorithmによるオフライン区間問い合わせ / 補助タグ: 座標・値の順序保存圧縮、Fenwick Tree・反転数・重み付き接頭辞統計
- ABC392 F「Insert」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ
- ABC396 F「Rotated Inversions」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC406 F「Compare Tree Weights」 公式問題主題: Euler順による部分木区間化 / 補助タグ
- ABC431 G「One Time Swap 2」 公式問題主題: ordered set・multisetの動的順序管理 / 補助タグ
- ABC436 F「Starry Landscape Photo」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC438 G「Sum of Min」 公式問題主題: gcd不変量・差分構造 / 補助タグ
- ABC439 F「Beautiful Kadomatsu」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: 座標・値の順序保存圧縮、Fenwick Tree・反転数・重み付き接頭辞統計、法上の四則演算・高速累乗・逆元
- ABC441 E「A > B substring」 公式問題主題: 一次元・二次元累積和と差分で区間情報を線形化する / 補助タグ
- ABC449 E「A += v」 公式問題主題: event順にactive集合を更新する / 補助タグ
- ABC452 F「Interval Inversion Count」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 補助タグ
- ABC461 E「E-liter」 公式問題主題: 反転数・重み付き接頭辞統計をFenwick Treeで保つ / 主タグ