Binary Indexed Tree (Fenwick Tree)
概要
セグメントツリーを左の子だけにして右の子を捨てたようなデータ構造です．セグメントツリーより実装も定数倍も軽いです． その分制限があり，和のように逆元が存在する演算なら任意の区間に対して使えますが，min のような演算に対しは左端からしか使えません．
計算量
$O(\log N)$
使い方
fenwick_tree<T> t(n)- サイズ
n，型Tの木を作る t.sum(l,r)- [
l,r) の和を求める t.add(i,a)- 0-indexed で
i番目の要素にaを足す
実装
template <class T>
struct fenwick_tree {
int n;
std::vector<T> x;
fenwick_tree(int n_ = 0) : n(n_), x(n + 1, 0) {}
int size() const { return n; }
T sum(int r) const {
T S = 0;
for (r = r - 1; r >= 0; r = (r & (r + 1)) - 1) S += x[r];
return S;
}
T sum(int l, int r) const { return sum(r) - sum(l); }
void add(int k, const T &a) {
for (; k < n; k |= k + 1) x[k] += a;
}
void set(int k, const T &a) { add(k, a - sum(k, k + 1)); }
};
template <class T>
struct fenwick_tree_range {
fenwick_tree<T> a, b;
fenwick_tree_range(int n = 0) : a(n), b(n) {}
int size() const { return a.size(); }
T sum(int r) const { return a.sum(r) + b.sum(r) * r; }
T sum(int l, int r) const { return sum(r) - sum(l); }
void add(int r, const T &x) {
a.add(r, x * r);
b.add(r, -x);
}
void add(int l, int r, const T &x) {
add(l, -x);
add(r, x);
}
};