Binary-Indexed Tree

template <typename T>
class BIT {
private:
    static const int MAXN = N + 100;
    T a[MAXN];

public:
    void add(int x, T d) {
        x++;
        while (x < MAXN) {
            a[x] += d;
            x += x & -x;
        }
    }
    T query(int x) {
        x++; T ret = 0;
        while (x) {
            ret += a[x];
            x -= x & -x;
        }
        return ret;
    }
    T query_interval(int a, int b) {
        // closed interval
        return query(b) - query(a - 1);
    } 

    /***** The following should be used exclusively *****/
    inline T query2(int x) {
        // used to query some value (not some sum)
        return query(x);
    }
    void add2(int a, int b, T d) {
        add(a, d); add(b + 1, -d);
    }
};