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);
    }
    int lower_bound(T x) {
        int ret = 0; T cnt = 0;
        int MAX = int(ceil(log(MAXN) / log(2)));
        for (int i = MAX; i >= 0; --i) {
            ret += 1 << i;
            if (ret > N || cnt + a[ret] >= x)
                ret -= 1 << i;
            else cnt += a[ret];
        }
        if (ret >= N) return INF;
        return max(ret, 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);
    }
};

namespace bit {
    using T = LL;
    const int M = -1;
    T c[M];
    inline int lowbit(int x) { return x & -x; }
    void add(int p, T v) {
        for (int i = p + 1; i < M; i += lowbit(i))
            c[i] += v;
    }
    T sum(int p) {
        T ret = 0;
        for (int i = p + 1; i > 0; i -= lowbit(i))
            ret += c[i];
        return ret;
    }
    int kth(T k) {
        int ret = 0;
        T cnt = 0;
        FORD (i, 20, -1) {
            ret += 1 << i;
            if (ret >= M || cnt + c[ret] >= k)
                ret -= 1 << i;
            else cnt += c[ret];
        }
        return ret + 1;
    }
}