Binary Indexed Tree/Fenwick Tree Template

For Leetcode use.

template <class T> 
class Bit { 
public: 
    // Usage: Bit<int> _bit; 
    Bit(const T n) : _sums(n+1, 0) {}
    void update(T i, T delta) { 
        while(i < _sums.size()) {
            _sums[i] += delta;
            i += lowbit(i); 
        }
    } 
    T query(T i) const { 
        T sum = 0;  
        while(i > 0) {
            sum += _sums[i];
            i -= lowbit(i);
        }  
        return sum; 
    }
private:
    static inline T lowbit(const T i) { 
        return i & (-i); 
    }
    vector<T> _sums; 
}; 

Leave a Reply

Your email address will not be published. Required fields are marked *

nineteen + 1 =

Note: Commenter is allowed to use '@+User+:' to automatically notify your reply to other commenter.