简述树状数组

树状数组可以解决大部分区间上面的修改以及查询的问题，例如1.单点修改，单点查询，2.区间修改，单点查询，3.区间查询，区间修改，换言之，线段树能解决的问题，树状数组大部分也可以。

 其修改和查询都是log级别的

树状数组的核心操作主要是修改单点和查询区间和

int tree[N];
int arr[N];
int lowbit(int k) {
	return k & -k;
}
void add_singleP(int pos, int k) {//一个点值增加，与其相关的父节点也修改
	for (int j = pos; j <= n; j += lowbit(j)) {
		tree[j] += k;
	}
}
inline int sumPre(int pos) {//得到区间[0,pos]前缀和
	int ans = 0;
	for (int j = pos; j != 0; j -= lowbit(j)) {
		ans += tree[j];
	}
	return ans;
}
inline int queryLR(int l, int r) {
	return sumPre(r) - sumPre(l - 1);
}

 将树状数组当成差分数组来看，修改区间和查询单点（差分的前缀和）

#include
using namespace std;
#define int long long 
#define rep(j,b,e) for(int j=(b);j<=(e);j++)
#define drep(j,e,b) for(int j=(e);j>=(b);j--)
const int N = 5e5 + 10;
int n, m, q, k;
int tree[N];
int arr[N];
int lowbit(int k) {
	return k & -k;
}
void add_singleP(int pos, int k) {//一个点值增加，与其相关的父节点也修改
	for (int j = pos; j <= n; j += lowbit(j)) {
		tree[j] += k;
	}
}
inline int sumPre(int pos) {//得到区间[0,pos]前缀和
	int ans = 0;
	for (int j = pos; j != 0; j -= lowbit(j)) {
		ans += tree[j];
	}
	return ans;
}
inline int queryLR(int l, int r) {
	return sumPre(r) - sumPre(l - 1);
}
 
signed main() {
#ifndef ONLINE_JUDGE
	//freopen("out.txt", "w", stdout);
#endif
	ios::sync_with_stdio(0); cout.tie(0);
	cin >> n >> m;
	rep(j, 1, n) {
		cin >> arr[j];
		add_singleP(j, arr[j] - arr[j - 1]);//树状数组元素作为差分
	}
	rep(j, 1, m) {
		int choice, x, y, k;
		cin >> choice;
		if (choice == 1) {
			cin >> x >> y >> k;
			add_singleP(x, k);
			add_singleP(y + 1, -k);//模拟差分标记区间
		}
		else {
			cin >> x;
			cout << sumPre(x) << endl;//差分的前缀和为该点的值
		}
	}
}

 树状数组求解逆序数，思路在注释。主要是离散化数组后，将数组元素当作树状数组下标利用树状数组每次统计比当前元素大有几个。，并记录求和。答案则为逆序数

#include
using namespace std;
#define int long long 
#define rep(j,b,e) for(int j=(b);j<=(e);j++)
#define drep(j,e,b) for(int j=(e);j>=(b);j--)
const int N = 5e5 + 10;
int n, m, q, k;
int tree[N];
struct node {
	int val, id;
};
node arr[N];
int ranks[N];
int lowbit(int k) {
	return k & -k;
}
void add_singleP(int pos, int k) {//一个点值增加，与其相关的父节点也修改
	for (int j = pos; j <= n; j += lowbit(j)) {
		tree[j] += k;
	}
}
inline int sumPre(int pos) {//得到区间[0,pos]前缀和
	int ans = 0;
	for (int j = pos; j != 0; j -= lowbit(j)) {
		ans += tree[j];
	}
	return ans;
}
inline int queryLR(int l, int r) {
	return sumPre(r) - sumPre(l - 1);
}
 
signed main() {
#ifndef ONLINE_JUDGE
	//freopen("out.txt", "w", stdout);
#endif
	ios::sync_with_stdio(0); cout.tie(0);
	cin >> n;
	rep(j, 1, n) {
		cin >> arr[j].val;
		arr[j].id = j;
	}
	int ans = 0;
//--离散化
	stable_sort(arr + 1, arr + 1 + n, [](node a, node b) {
		if (a.val != b.val)
			return a.val > b.val;
		return a.id > b.id;//保证靠后的相同数不会把靠前的相同数当逆序
		});
	rep(j, 1, n) {
		ranks[arr[j].id] = j;//离散化
	}
//--
	rep(j, 1, n) {//更大的数字先入树状数组，每次统计前面有几个比自己大的
		int x = ranks[j];
		add_singleP(x, 1);
		ans += sumPre(x - 1);
	}
	cout << ans;
}