binary indexed treee code example

Example: binary indexed tree

template<class T> class BIT {

    vector<T> bit;
public:
    BIT (int size) : bit(vector<T>(size+1)) {}
    BIT (vector<T>& v) : bit(vector<T>(v.size()+1)) {
        for (int i = 0; i<v.size(); ++i) {
            update(i, v[i]);
        }
    }
    T sum (int i) {
        ++i;
        T s = 0;
        while (i>0) {
            s += bit[i];
            i -= i&-i;
        }
        return s;
    }
    void update (int i, T u) {
        ++i;
        while (i<bit.size()) {
            bit[i] += u;
            i += i&-i;
        }
    }

};