fenwick tree

ソースコード

  1#include <iostream>
  2#include <vector>
  3#include <cassert>
  4using namespace std;
  5
  6// FenwickTree
  7namespace titan23 {
  8
  9    template<typename T>
 10    struct FenwickTree {
 11        int _n, _s;
 12        vector<T> _tree;
 13
 14        FenwickTree(const int n) {
 15            _n = n;
 16            _s = 1 << (32 - __builtin_clz(_n));
 17            _tree.resize(n+1, 0);
 18        }
 19
 20        FenwickTree(const vector<T> &a)
 21                 : _n(a.size()),
 22                   _s(1 << (32 - __builtin_clz(_n-1))),
 23                   _tree(_n+1, 0) {
 24            for (int i = 1; i <= _n; ++i) _tree[i] = a[i-1];
 25            for (int i = 1; i < _n; ++i) {
 26                if (i + (i & (-i)) <= _n) {
 27                    _tree[i + (i & (-i))] += _tree[i];
 28                }
 29            }
 30        }
 31
 32        T pref(int r) const {
 33            T res = 0;
 34            while (r > 0) {
 35                res += _tree[r];
 36                r -= r & (-r);
 37            }
 38            return res;
 39        }
 40
 41        T suff(int l) const {
 42            return pref(_n) - pref(l);
 43        }
 44
 45        T sum(const int l, const int r) const {
 46            return pref(r) - pref(l);
 47        }
 48
 49        void add(int k, const T x) {
 50            ++k;
 51            while (k <= _n) {
 52                _tree[k] += x;
 53                k += k & (-k);
 54            }
 55        }
 56
 57        T get(const int k) const {
 58            return pref(k+1) - pref(k);
 59        }
 60
 61        void set(const int k, const T x) {
 62            T pre = get(k);
 63            add(k, x-pre);
 64        }
 65
 66        int bisect_left(T w) const {
 67            int i = 0, s = _s;
 68            while (s) {
 69                if (i+s <= _n && _tree[i+s] < w) {
 70                    w -= _tree[i+s];
 71                    i += s;
 72                }
 73                s >>= 1;
 74            }
 75            return (w ? i : -1);
 76        }
 77
 78        int bisect_right(T w) const {
 79            int i = 0, s = _s;
 80            while (s) {
 81                if (i+s <= _n && _tree[i+s] <= w) {
 82                w -= _tree[i+s];
 83                i += s;
 84                }
 85                s >>= 1;
 86            }
 87            return i;
 88        }
 89
 90        vector<T> tovector() const {
 91            vector<T> sub(_n+1), res(_n);
 92            for (int i = 0; i <= _n; ++i) sub[i] = pref(i);
 93            for (int i = 0; i < _n; ++i) res[i] = sub[i+1] - sub[i];
 94            return res;
 95        }
 96
 97        void print() const {
 98            vector<T> fw = tovector();
 99            cout << "[";
100            for (int i = 0; i < _n-1; ++i) cout << fw[i] << ", ";
101            cout << fw[_n-1] << "]\n";
102        }
103    };
104}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/fenwick_tree.cpp