fenwick_tree.hpp

// fenwick tree {{{ 
template < typename data_type >
class fenwick_tree {

    std::size_t size_;
    std::vector< data_type > data_;

    public:
    fenwick_tree(size_t size) : size_(size), data_(size + 1) {}

    data_type get_sum(int k) {
        data_type sum = 0;
        for (; k; k -= k & -k) sum += data_[k];
        return sum;
    }

    void add(int k, data_type x) {
        for (; k <= size_; k += k & -k) data_[k] += x;
    }
};
// }}}