树状数组(Fenwick Tree)是一种用于高效计算前缀和的数据结构,具有较小的内存占用和较快的查询、更新操作。它广泛应用于解决一维数组的区间查询问题。

树状数组的原理基于二进制的思想。假设有一个长度为nn的数组AA,树状数组就是用一个长度为nn的辅助数组CC来模拟AA数组的前缀和。数组CC的索引ii表示原数组AA的前ii个元素的和,数组CC的值表示AA数组对应前缀的和。

树状数组的核心操作有两个:区间和查询和单点更新。

区间和查询:给定一个区间[l,r][l,r],要求计算出原数组A[l,r]A[l,r]的和。使用树状数组的查询操作如下:
1. 初始化一个变量sumsum为0。
2. 从rr开始,将rr的最低位的11置为00(即r=r(r&r)r=r-(r\&-r)),并将sumsum加上C[r]C[r]的值。
3. 重复步骤2,直到rr为0。
4. 从ll开始,将ll的最低位的11置为00(即l=l(l&l)l = l - (l \& -l)),并将sumsum减去C[l]C[l]的值。
5. 重复步骤4,直到ll00
6. 返回sumsum

单点更新:给定一个索引ii和一个增量deltadelta,要求将原数组A[i]A[i]的值加上deltadelta。使用树状数组的更新操作如下:
1. 从ii开始,将ii的最低位的11加上deltadelta(即i=i+(i&i)i = i + (i \& -i))。
2. 重复步骤11,直到ii大于数组长度nn

通过这两个核心操作,可以高效地实现对原数组的区间查询和单点更新。

需要注意的是,树状数组的索引从11开始,因此在使用时需要对原始数据进行适当的处理。同时,树状数组只能处理非负数据,对于负数的处理需要进行适当的转换或者使用其他数据结构。

例题1:求每个数在数组中的逆序数和总逆序数

给定一个 1N1∼N 的随机排列,要求一次只能交换相邻两个数,那么最少需要交换多少次才可以使数列按照从小到大排列呢?

请你求出一个待排序序列的最少交换次数和对应的逆序数列

输入格式

第一行一个整数NN

第二行一个1N1∼N的排列。

输出格式

第一行输出逆序数列,数之间用空格隔开。

第二行输出最少交换次数。

数据范围

1N10001≤N≤1000

输入样例:

1
2
8
4 8 2 7 5 6 1 3

输出样例:

1
2
6 2 5 0 2 2 1 0
18

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int a[N], tr[N];
int f[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int ask(int x)
{
LL res = 0;
for(int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++)
{
int y = a[i];
f[y] = ask(n) - ask(y);
add(y, 1);
}
int res = 0;
for(int i = 1; i <= n; i ++)
{
cout << f[i] << " ";
res += f[i];
}
cout << endl << res;
return 0;
}

1、f[N]f[N]数组存储的是所有在i前面,比a[i]a[i]小的数据

2、样例解释:第一个的逆序对为什么为6,因为求的是就是数值为1的逆序对数量,在1前面有6个数比1大,所以逆序对为6

转载自这里