ACM algorithms

acm_template.cpp

///////////////////////////////////////////////////////
// Binary Indexed Tree 树状数组
///////////////////////////////////////////////////////
#include <cassert>

template<typename T, int N> class BIT {
public:
    T c[N];
    void init() { memset(c, 0, sizeof(c)); }
    int lowbit(int x) { return x & (-x); }
    void add(int i, int x) {
        while(i < N) {
            c[i] += x;
            i += lowbit(i);
        }
    }
    T query(int x) {  
        assert(x<N);
        T sum=0;
        while(x > 0) {
            sum += c[x];
            x -= lowbit(x);
        } 
        return sum; 
    }
};

// Usage:
// BIT<int, N> bitree;
// bitree.init();
// bitree.add(2, 3);
// bitree.query(3);

///////////////////////////////////////////////////////