Binary Indexed Tree (BIT)

#include<bits/stdc++.h>
#define ll long long

// Note:
//      1. Index from 1 -> n
//      2. all values are INT (NOT long long)
template <typename T> 
struct BITSum 
{
    int n;
    T *BIT;
    
    BITSum () {}
    void init (int n_) {
        n = n_;
        BIT = new T[n + 1];
        fill(BIT, BIT + n + 1, 0);
    }

    void clear() {
        fill(BIT, BIT + n + 1, 0);
    }
    
    // all index from idx to n get added by v
    void update(int idx, T v) { 
        while (idx <= n) {
            BIT[idx] += v;
            idx += (idx & (-idx));
        }
    }
    
    // point query
    T getsum(int idx) { 
        T ret = 0;
        while (idx > 0) {
            ret += BIT[idx];
            idx -= (idx & (-idx));
        }
        return ret;
    }
};