『算法-ACM 竞赛-算法-数据结构』信息竞赛进阶指南-树状数组 （模板)

写在前面：
我们是主要是讲算法模板，即实现的代码，并不讲实现的原理

什么是树状数组？

树状数组(Binary Indexed Tree(B.I.T), Fenwick
Tree)是一个查询和修改复杂度都为 log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在 log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。

图呢就是这个形状的：

// [1,x]分成的O(log(x))个小区间
while (x > 0) {
	printf("[%d, %d]\n", x - (x & -x) + 1, x);
	x -= x & -x;
}

// 树状数组查询前缀和
int ask(int x) {
	int ans = 0;
	for (; x; x -= x & -x) ans += c[x];
	return ans;
}

// 树状数组单点增加
void add(int x, int y) {
	for (; x <= N; x += x & -x) c[x] += y;
}

// 树状数组求逆序对
for (int i = n; i; i--) {
	ans += ask(a[i]);
	add(a[i], 1);
}