-

2021年1月26日发(作者：后浪推前浪)
树状数组，具体的说是

离散化
+
树状数组。这也是学习树状数组的第一题
.
算法的大体流程就是：

1.
先对输入的数组离散化，使得各个元素比较接近，而不是离散的，

2.
接着，运用树状数组的标准操作来累计数组的逆序数。

算法详细解释：

1.
解释为什么要有离散的这么一个过程？


刚开始以为
999.999.999
这么一个数字，对于
i nt
存储类型来说是足够了。


还有只有
500000
个数字，何必要离散化呢？


刚开始一直想不通，后来明白了，后面在运用树状数组操作的时候，


用到的树状数组
C[i]
是建立在一个有点像位存储的数组的基础之上的，


不是单纯的建立在输入数组之上。


比如输入一个
9 1 0 5 4
，那么
C[i]
树状数组的建立是在，


下标

0 1 2 3 4 5 6 7 8 9

数组

1 1 0 0 1 1 0 0 0 1

现在由 于
999999999
这个数字相对于
500000
这个数字来说是很大的，


所以如果用数组位存储的话，那么需要
999999999
的空间来存储输入的数据。


这样是很浪费空间的，题目也是不允许的，所以这里想通过离散化操作，


使得离散化的结果可以更加的密集。

2.
怎么对这个输入的数组进行离散操作？


离散化是一种常用的技巧，有时数据范围太大，可以用来放缩到我们能处理的范围；


因为其中需排序的数的范围
0---999 999 999
；显然数组不肯能这么大；


而
N
的最大范围是
500 000
；故给出的数一定可以与
1.
。。。
N
建立一个一一映射；


①当然用
map
可以建立，效率可能低点；


②这里用一个结构体


struct Node

{

int v,ord;

}p[510000];
和一个数组
a[510000];

其中
v
就是原输入的值，
ord
是下标；然后对结构体按
v
从小到大排序；


此时，
v
和结构体的下标就是一个一一对应关系，而且满足原来的大小关系；


for(i=1;i<=N;i++) a[p[i].ord]=i;

然后
a
数组就存储了原来所有的大小信息；


比如

9 1 0 5 4 -------
离散后
aa
数组就是

5 2 1 4 3
；


具体的过程可以自己用笔写写就好了。

3.
离散之后，怎么使用离散后的结果数组来进行树状数组操作，计算出逆序数？


如果数据不是很大，

可以一个个插入到树状数组中，


每插入一个数，

统计比他小的数的个数，


对应的逆序为

i- getsum( aa[i] ),

其中

i
为当前已经插入的数的个数，


getsum( aa[i]
）为比

aa[i]
小的数的个数
,

i- sum( aa[i] )
即比

aa[i]
大的个数，

即逆序的个数


但如果数据比较大，就必须采用离散化方法


假设输入的数组是
9 1 0 5 4
，

离散后的结果
aa[] = {5,2,1,4,3};
在离散结果中间结果的基础上，那么其计算逆序数的过程是这么一个过程。

1
，输入
5
，

调用
upDate(5, 1),
把第
5
位设置为
1
1 2 3 4 5
0 0 0 0 1
计算
1-5
上比
5
小的数字存在么？

这里用到了树状数组的
getSum
（
5
）

= 1
操作，

现在用输入的下标
1 - getSum(5) = 0
就可以得到对于
5
的逆序数为
0
。

2.
输入
2
，

调用
upDate(2, 1),
把第
2
位设置为
1
1 2 3 4 5
0 1 0 0 1
计算
1-2
上比
2
小的数字存在么？

这里用到了树状数组的
getSum
（
2
）

= 1
操作，

现在用输入的下标
2 - getSum(2) = 1
就可以得到对于
2
的逆序数为
1
。

3.
输入
1
，

调用
upDate(1, 1),
把第
1
位设置为
1
1 2 3 4 5
1 1 0 0 1
计算
1-1
上比
1
小的数字存在么？

这里用到了树状数组的
getSum
（
1
）

= 1
操作，

现在用输入的下标

3 - getSum(1) = 2
就可以得到对于
1
的逆序数为
2
。

4.
输入
4
，

调用
upDate(4, 1),
把第
5
位设置为
1

-

-

-

-

-

-

-

-