BIT - 競プロライブラリ

BinaryIndexedTree

点更新と区間[0,i)に対するクエリをそれぞれO(logN)でできるデータ構造
i&-iでiで1の最下位bitが取得できるのをつかって実装
単位元と更新クエリ、区間クエリに使う式を指定する
デフォルト引数のまま使うとよくある和を求めるBIT
わかりやすいスライド

// Binary Indexed Tree
// 0-indexed
template <typename T>
class BIT {
private:
  vector<T> bit;
  // 単位元
  int neutral = 0;
  // 更新クエリ, 区間クエリ
  function<T(T,T)> f = [](const T l, const T r) { return l+r; };
  function<T(T,T)> g = [](const T l, const T r) { return l+r; };
public:
  // 初期化
  BIT(int neu = 0,
    function<T(T,T)> _f = [](const T l, const T r) { return l+r; },
    function<T(T,T)> _g = [](const T l, const T r) { return l+r; },
    int n = 1e5)
  {
    init(neu, _f, _g, n);
  }
  void init(int neu = 0,
    function<T(T,T)> _f = [](const T l, const T r) { return l+r; },
    function<T(T,T)> _g = [](const T l, const T r) { return l+r; },
    int n = 1e5)
  {
    neutral = neu; f = _f; g = _g;
    bit.assign(n+5, neutral);
  }
  // iに対する点更新クエリ
  void update(int i, T w) {
    for(int x = i+1; x < bit.size(); x += x&-x) bit[x] = f(bit[x], w);
  }
  // [0,i)に対する区間クエリ
  T query(int i) {
    T ret = neutral;
    for(int x = i+1; x > 0; x -= x & -x) ret = g(ret, bit[x]);
    return ret;
  }
};

転倒数

バブルソートの交換回数⇔i<j,a[i]>a[j]であるような(i,j)の組
i番目より前でa[i]より大きい数の個数を求めたい
BITでa[i]の個数をもっておいて足していけばよい
動的累積和みたいな気持ち
https://chokudai_s001.contest.atcoder.jp/tasks/chokudai_S001_j

直線の交点の数とかを転倒数に落とせる atcoderのどこかで見た

集合のX番目の数

転倒数と同じくa[i]の個数を持っておく
[0,val)の個数がO(logN)で求まるので二分探索を使えばX番目の数が求まる
N<=10^5,a[i]<=10^9みたいなときも要素の値が関係なく大小関係だけ気にすればいいので座標圧縮をすればok
https://arc033.contest.atcoder.jp/tasks/arc033_3

区間加算クエリ

差分を取ると区間加算が2点加算になることを使う
BITを2本もつ

2次元BIT

蟻本p162