Fenwick Tree

Fenwick Tree

template <typename T>
struct Fenwick { // 1-indexed
    T *data;
    int FMAX;
    void init(int N) { // Range: [1, N]
        FMAX = N;
        data = new T[FMAX + 2];
        memset(data, 0, sizeof(T) * (FMAX + 2));
    }
    void update(int idx, T v) {
        for(; idx <= FMAX; idx += idx & -idx) data[idx] += v;
    }
    T get(int idx) {
        T res = 0;
        for(; idx > 0; idx = idx & (idx - 1)) res += data[idx];
        return res;
    }
};

Time Complexity

• Init: $O(N)$
• Update: $O(\log N)$
• Get: $O(\log N)$