Binary Indexed Tree

BITはセグメント木の機能を限定したものであり、実装が簡単でメモリを節約できる

//数列a(a[0],a[1],…,a[n-1])についての区間和と点更新を扱う
//区間和,点更新,二分探索はO(log{n})で動作する
class BIT {
public:
    //データの長さ
    ll n;

    //データの格納先
    vector<ll> a;//(1の最小bitの桁)個数分の範囲和を持つ

    //コンストラクタ
    BIT(ll n) :n(n), a(n + 1, 0) {}

    //a[i]にxを加算する
    void add(ll i, ll x) {
        i++;
        if (i == 0) return;
        for (ll k = i;k <= n;k += (k & -k)) {//下から上
            a[k] += x;
        }
    }

    //a[i]+a[i+1]+…+a[j]を求める
    ll sum(ll i, ll j) {
        return sum_sub(j) - sum_sub(i - 1);
    }

    //a[0]+a[1]+…+a[i]を求める
    ll sum_sub(ll i) {
        i++;
        ll s = 0;
        if (i == 0) return s;

        for (ll k = i;k > 0;k -= (k & -k)) {//上から下
            s += a[k];
        }
        return s;
    }

    //a[0]+a[1]+…+a[i]>=xとなる最小のiを求める(任意のkでa[k]>=0が必要)
    ll lower_bound(ll x) {
        if (x <= 0) {
            //xが0以下の場合は該当するものなし→0を返す
            return 0;
        }
        else {
            ll i = 0;ll r = 1;
            //最大としてありうる区間の長さを取得する
            //n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める
            while (r < n) r = r << 1;
            //区間の長さは調べるごとに半分になる
            for (int len = r;len > 0;len = len >> 1) {
                //その区間を採用する場合
                if (i + len < n && a[i + len] < x) {
                    x -= a[i + len];
                    i += len;
                }
            }
            return i;
        }
    }
};