关于树状数组

看到log n，很容易猜到树状数组利用了二分的思想。c数组的每一项，表示了在这一项的“管辖范围”（图中实线所连接的点）之内的元素之和；而当要查询比如区间[1, 7]时，可以将它拆分成c[4]+c[6]+c[7]。

那么如何确定一个数的管辖范围，又如何拆分呢？不妨看一下对 i 的二进制而言，c[i]的管辖范围有什么特点。

许多其他博客都有对这个的讲解，这里就不再多说了。

inline int lowbit(int i) {
    return i & (-i);
}

至于为什么，暂时还没有找到一个清晰而且容易理解的证明……不过举几个例子很容易验证。

void modify(int x, int add) {
    do c[x] += add;
    while ((x += lowbit(x)) <= n);
}

int q(int r) {
    int sum = 0;
    do sum += c[r];
    while (r -= lowbit(r));
}
inline int q_range(int l, int r) {
    return q(r) - q(l - 1);
}

struct cmp {
    bool operator()(int x, int y) {
         return a[x] > a[y];
    }
}
 
int main() {
    //读入数据到a数组中
    for (int i = 0; i < n; ++i)
        h[i] = i;
    sort(h, h + n, cmp());
    //继续下面的操作
}

#include<iostream>
#include<algorithm>
#include<numeric>
using namespace std;
 
//l[i]是左侧小于a[i]的数的个数；r[i]是右侧大于a[i]的数的个数
//c是l的树状数组，C是r的树状数组，n是数列长度，其余字母如上
int c[30010], C[30010], a[30010], h[30010], n, l[30010], r[30010], k[30010];
struct cmp { bool operator()(int x, int y) {return a[x] < a[y];}};
 
void p(int* w, int x) {do ++w[x]; while ((x += (x & (-x))) <= n);}
int q(int* w, int x) { int s = 0; do s += w[x]; while (x -= (x & (-x))); return s; } //树状数组基本操作；p:单点修改 q:区间查询
 
void unique() { //给重复数字同一编号
    int d = k[h[1]] = 1;
    for (int i = 2; i <= n; ++i) {
        if (a[h[i]] != a[h[i - 1]]) ++d;
        //如果不同，编号自增；也就是说，如果相同就会有同一编号
        k[h[i]] = d;
    }
}
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], h[i] = i;
    sort(h + 1, h + n + 1, cmp()); unique() //离散化
    for (int i = 1; i <= n; ++i)
        p(c, k[i]), l[i] = q(c, k[i] - 1); //注意查询左边区间和的时候并不包括自己，因此要用k[i] - 1
    for (int i = n; i >= 1; --i)
        p(C, k[i]), r[i] = n - i - q(C, k[i]) + 1; //这里要查询的是右边的区间和，可以用总和(也就是n-i+1)减去左边的区间和q(C, k[i])
    cout << inner_product(l + 2, l + n, r + 2, 0) << endl;
    return 0;
}