树状数组的概念

树状数组是一种利用数的二进制特征进行检索的树状结构。

树状数组基础

长度为 n 的数列{a1,a2,a3,a4,....,an}，进行以下操作：

单点修改：(x, val)，把 ax 加上 x。注：该点值修改完之后，会把值压缩给后面（箭头指向）的点。
区间查询：（r）表示询问区间 [1, r] 的元素和。注：对前面（箭头指向）的压缩点求和。
例如，r = 14（1110），sum(r) = 14(1100) + 12(1100) + 8(1000) , 两幅图要结合着看。

const int maxn = 1e6+1;

int tree[maxn];

void add(int x, int val, int n) { // 单点修改 注意：单点修改时原数组一定要修改
    for(int i = x; i <= n; i += i&-i) {
        tree[i] += val;
    }
}

int sum(int r) { // 区间查询
    int res = 0;
    for(int i = r; i; i -= i&-i) {
        res += tree[i];
    }
    return res;
}

树状数组拓展

长度为 n 的非负整数数列{a1,a2,a3,a4,....,an}，进行以下操作：
1.单点查询:（val）查询前缀和为 val 的点。注：查询的关键在于单调性和数据结构。
图片说明
注：若 tree(x) >= val ，则标记为红点并向上查询，若 tree(x) < val，则标记为绿点并向次上查询，返回最后一个绿点+1，即最后一个红点。

int get(int val, int n) { // 单点查询 注意：二进制运算要加括号
    int x = 0; //取值范围 (0,n)
    for(int i = (1<<(31-__builtin_clz(n))); i; i >>= 1) { // i初始为n的最高位1
        if ((x^i) > n) continue; // 大于 n 的点并未初始化
        if (tree[x^i] < val) { // 二分树状数组
            val -= tree[x^i];
            x ^= i;
        }
    }
    return x+1; // 返回范围（1，n+1）
}