fenwick_tree.h

#ifndef FENWICK_TREE_H
#define FENWICK_TREE_H
 
#ifdef __cplusplus
#include <iostream>
#include <vector>
#endif

template <typename T> struct fenwick_tree {
    std::vector<T> tree;
    int n;

    inline explicit fenwick_tree(const std::vector<T>& v) noexcept : n(int(v.size())) {
        tree = std::vector<T>(n, 0);
        for (int i = 0; i < n; i++) {
            this->update(i, v[i]);
        }
    }

    inline T sum(int k) {
        T sum = 0;
        for (; k >= 0; k = (k & (k + 1)) - 1) {
            sum += tree[k];
        }
        return sum;
    }

    inline T sum(int a, int b) { return sum(b) - sum(a - 1); }

    inline void update(int k, int x) {
        for (; k < n; k = k | (k + 1)) {
            tree[k] += x;
        }
    }
};
 
#endif