【数据结构】树状数组（简单名次树）

struct BinaryIndexTree {

    static const int MAXN = 500000 + 10;

    int n, A[MAXN];
    int cnt[MAXN], siz[MAXN];

    void InitValue() {
        n = 0;
    }

    void UseValue(int val) {
        A[++n] = val;
    }

    void Init() {
        sort(A + 1, A + 1 + n);
        n = unique(A + 1, A + 1 + n) - (A + 1);
        memset(siz, 0, sizeof(siz[0]) * (n + 1));
    }

    void Insert(int val, int num) {
        int pos = lower_bound(A + 1, A + 1 + n, val) - A;
        cnt[pos] += num;
        for(int i = pos; i <= n; i += i & (-i))
            siz[i] += num;
    }

    void Remove(int val, int num) {
        int pos = lower_bound(A + 1, A + 1 + n, val) - A;
        num = min(cnt[pos], num);
        cnt[pos] -= num;
        for(int i = pos; i <= n; i += i & (-i))
            siz[i] -= num;
    }

    int GetRank(int val) {
        int pos = lower_bound(A + 1, A + 1 + n, val) - A, res = 1;
        for(int i = pos - 1; i; i -= i & (-i))
            res += siz[i];
        return res;
    }

} bit;

【数据结构】树状数组（简单名次树）

原文：https://www.cnblogs.com/purinliang/p/14265133.html