Binary Indexed Tree
(structure/BIT.cpp)

• View this file on GitHub
• Last update: 2021-09-12 23:44:25+09:00

概要

Binary Indexed Tree (Fenwick Tree)

1点更新区間取得ができるデータ構造。和しか実装してないけど多分それくらいしか使わないはず？

• add(x,y) : x 番目の要素にy を足す
• sum(l,r) : [l,r) の和
• lower_bound(w) : [0,x] の和がw 以上となる最小のindex

計算量

全て $O(log\ N)$

Depends on

• template/template.cpp

Verified with

• test/BIT.test.cpp

Code

#pragma once
#include "../template/template.cpp"

template <class T>
class BIT {
    ll N;
    vector<T> bit;
    void add_(ll x, T y) {
        while (x <= N) {
            bit[x] += y;
            x += x & -x;
        }
    }
    T sum_(ll x) {
        T res = 0;
        while (x > 0) {
            res += bit[x];
            x -= x & -x;
        }
        return res;
    }

   public:
    ll lower_bound(T w) {
        if (w <= 0) return -1;
        ll x = 0;
        ll k = 1;
        while (k * 2 <= N) k *= 2;
        for (; k > 0; k /= 2) {
            if (x + k <= N && bit[x + k] < w) {
                w -= bit[x + k];
                x += k;
            }
        }
        return x;
    }
    void add(ll x, T y) { add_(x + 1, y); }
    T sum(ll l, ll r) { return sum_(r) - sum_(l); }
    BIT(ll x) : N(x), bit(x + 1) {}
};
/*
@brief Binary Indexed Tree
@docs docs/BIT.md
*/

#line 2 "template/template.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, n) for (int i = 1; i < n; i++)
#define rev(i, n) for (int i = n - 1; i >= 0; i--)
#define REV(i, n) for (int i = n - 1; i > 0; i--)
#define all(v) v.begin(), v.end()
#define PL pair<ll, ll>
#define PI pair<int, int>
#define pi acos(-1)
#define len(s) (int)s.size()
#define compress(v) \
    sort(all(v));   \
    v.erase(unique(all(v)), v.end());
#define comid(v, x) lower_bound(all(v), x) - v.begin()

template<class T>
using prique=priority_queue<T,vector<T>,greater<>>;

template <class T, class U>
inline bool chmin(T &a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U>
inline bool chmax(T &a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
constexpr ll inf = 3e18;
#line 3 "structure/BIT.cpp"

template <class T>
class BIT {
    ll N;
    vector<T> bit;
    void add_(ll x, T y) {
        while (x <= N) {
            bit[x] += y;
            x += x & -x;
        }
    }
    T sum_(ll x) {
        T res = 0;
        while (x > 0) {
            res += bit[x];
            x -= x & -x;
        }
        return res;
    }

   public:
    ll lower_bound(T w) {
        if (w <= 0) return -1;
        ll x = 0;
        ll k = 1;
        while (k * 2 <= N) k *= 2;
        for (; k > 0; k /= 2) {
            if (x + k <= N && bit[x + k] < w) {
                w -= bit[x + k];
                x += k;
            }
        }
        return x;
    }
    void add(ll x, T y) { add_(x + 1, y); }
    T sum(ll l, ll r) { return sum_(r) - sum_(l); }
    BIT(ll x) : N(x), bit(x + 1) {}
};
/*
@brief Binary Indexed Tree
@docs docs/BIT.md
*/

Back to top page