Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Binary Indexed Tree
- // 0-indexed
- template <typename T>
- class BIT {
- private:
- vector<T> bit;
- // 単位元
- int neutral = 0;
- // 更新クエリ, 区間クエリ
- function<T(T,T)> f = [](const T l, const T r) { return l+r; };
- function<T(T,T)> g = [](const T l, const T r) { return l+r; };
- public:
- // 初期化
- BIT(int neu = 0,
- function<T(T,T)> _f = [](const T l, const T r) { return l+r; },
- function<T(T,T)> _g = [](const T l, const T r) { return l+r; },
- int n = 1e5)
- {
- init(neu, _f, _g, n);
- }
- void init(int neu = 0,
- function<T(T,T)> _f = [](const T l, const T r) { return l+r; },
- function<T(T,T)> _g = [](const T l, const T r) { return l+r; },
- int n = 1e5)
- {
- neutral = neu; f = _f; g = _g;
- bit.assign(n+5, neutral);
- }
- // iに対する点更新クエリ
- void update(int i, T w) {
- for(int x = i+1; x < bit.size(); x += x&-x) bit[x] = f(bit[x], w);
- }
- // [0,i)に対する区間クエリ
- T query(int i) {
- T ret = neutral;
- for(int x = i+1; x > 0; x -= x & -x) ret = g(ret, bit[x]);
- return ret;
- }
- };
Add Comment
Please, Sign In to add comment