树状数组求逆序对c语言
时间: 2023-11-07 12:58:46 浏览: 44
以下是使用树状数组求解逆序对的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100005
int n;
int a[MAXN];
int c[MAXN];
struct Node {
int val, index;
} b[MAXN];
int lowbit(int x) {
return x & (-x);
}
int cmp(const void *a, const void *b) {
return ((Node *)a)->val - ((Node *)b)->val;
}
int sum(int x) {
int ans = 0;
while (x > 0) {
ans += c[x];
x -= lowbit(x);
}
return ans;
}
void update(int x) {
while (x <= n) {
c[x]++;
x += lowbit(x);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[i].val = a[i];
b[i].index = i;
}
qsort(b + 1, n + 1, sizeof(b[0]), cmp);
for (int i = 1; i <= n; i++) {
a[b[i].index] = i;
}
long long ans = 0;
for (int i = n; i >= 1; i--) {
ans += sum(a[i] - 1);
update(a[i]);
}
printf("%lld\n", ans);
return 0;
}
```
其中,我们使用了一个辅助数组b来存储每个数的值和它在原数组中的下标,然后将b按照值的大小排序,得到一个新的数组a,其中a[i]表示原数组中第i个数的排名。接着,我们从后往前遍历a,每次将a[i]-1(即比a[i]小的数的个数)加入答案中,并更新a[i]的位置。具体来说,我们可以使用树状数组来维护前缀和,用sum(a[i]-1)来查询比a[i]小的数的个数,用update(a[i])来更新a[i]的位置。最终,答案就是所有查询结果的和。