Binary Indexed Tree (a.k.a. Fenwick tree)

BIT.cc

#define MAXBIT  1000000
#define lowbit(x)   (x & -x)

struct BIT {
    int bit[MAXBIT];
    int M;

    void clear(int M) {
        memset(bit, 0, sizeof(bit));
        this->M = M;
    }

    // require: x > 0
    void add(int x, int key) {
        for (; x <= M; x += lowbit(x)) bit[x] += key;
    }

    // require: x > 0
    int query(int x) {
        int ret = 0;
        for (; x; x -= lowbit(x)) ret += bit[x];
        return ret;
    }
};


int solve() {
    Left.clear(); Right.clear();
    return 0;
}