典型タグ

Fenwick Tree・反転数・重み付き接頭辞統計

値や座標の頻度を動的な接頭辞和で数えて反転数を求めるか、複数本を組み合わせて次数付きの区間式を評価する。

この典型を扱う単元: 反転数・重み付き接頭辞統計をFenwick Treeで保つ

検索別名: BIT、Binary Indexed Tree、フェニック木

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

扱う対象
  • prefix
  • 反転数
  • 添字付き和
  • 配列
  • 重み
  • 頻度
使う手掛かり
  • point update
  • 一点更新
  • 左側に大きい値
  • 接頭辞和
  • 累積和
保つ不変量
  • bit
  • 係数
  • 処理済み頻度
  • 複数本の
求めるもの
  • query
  • 動的和
  • 区間式
  • 反転数
適用しない条件
  • bit.?dp
  • bit.?mask
  • bitset
分類・前提・学習成果

分類と直接の前提

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

関連する典型

学習成果と学習単位

代表問題

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

関連問題

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