ホーム > libalgo

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);
    }
};

参考文献

検証

AOJ DSL2B (Submission)