Range tree

// range tree
// nasarouf@cs.ubc.ca

#define BASE (1<<17)
#define MAX ((BASE)*2)
template<class INT>
class BIT{
    INT bit[MAX];
public:
    inline INT sum(int pos){
        INT ret=0,b=BASE;
        if (pos==BASE-1) return bit[1];
        for (pos+=b; pos && pos>=b; )
            if (pos%2==0) ret+=bit[pos--];
            else{ pos/=2; b/=2; }
        return ret;
    }
    inline const INT& get(int pos){ return bit[pos+BASE]; }
    inline void add(int pos, INT c){
        for (pos+=BASE; pos; pos/=2) bit[pos]+=c;
    }
    inline const INT& operator[](int pos){ return get(pos); }
};