Fenwick Tree

概要

別名 Binary Indexed Tree ( BIT )。

method

• ???

Program

struct BIT{
    public:
        BIT(ll _n){
            n = _n;
            data.resize(n);
        }
        void add(ll i,ll x){
            i++; // 1-indexed (LSBを用いる都合上)
            while(i <= n){
                data[i-1] += x;
                i += (i & -i); // LSBを足した先にも考慮
            }
        }
        ll sum(ll l,ll r){
            return _sum(r) - _sum(l); // 裏関係
        }

    private:
        ll n;
        vector<ll> data;
        ll _sum(ll i){
            ll s = 0;
            // ここのiは1-indexed
            while(i){
                s += data[i-1];
                i -= (i & -i);
            }
            return s;
        }
};