浅谈Fenwick Tree树状数组

树状数组或二元索引树(BIT, Binary Indexed Tree)作为一种高效计算数组前缀和的数据结构,又以其发明者被命名为Fenwick Tree

abstract.jpeg

楔子

给定一个数组a:2、1、7、5

在进行单点更新操作时,得益于索引下标其时间复杂度为O(1)。例如:a[2] = 996
而如果需要计算该数组的前缀和,则需要进行遍历。其时间复杂度为O(n)。例如:sum[2]=a[0]+a[1]+a[2]=2+1+7=10

那如果换个思路,我们将原数组转换为相应的前缀和数组s:2、3、10、15
此时期望获取原数组a的前缀和,则可直接通过前缀和数组的索引下标进行获取,其时间复杂度为O(1)。例如:s[2]=10
但在进行单点更新时,由于我们需要维护前缀和数组s,故需要遍历该数组、并将增量更新到相应元素上。其时间复杂度为O(n)。例如,将原数组索引为1的元素减小2。则:

s[1]=3-2=1
s[2]=10-2=8
s[3]=15-2=13

那如何能够同时兼顾单点更新与前缀和这两种操作的在时间上的效率呢?答案就是下面所要介绍的Fenwick Tree树状数组。其能够实现在单点更新、前缀和操作上的对数时间复杂度

lowbit函数

而在介绍Fenwick Tree树状数组之前,我们先来介绍一个前置知识。如何计算非负整数n在二进制表示下最低位1及其后面的0所构成的数值,为后续行文方便记为lowbit函数。举个例子,172在二进制下可以表示为10101100,则我们期望lowbit(127) = 0b100 = 4

而lowbit函数的实现则可通过位运算,具体如下所示。其中,方式1与方式2本质上是等价的。因为负数在计算机中是用补码表示的,即对正数进行取反再加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 非负整数n在二进制表示下最低位1及其后面的0所构成的数值
* @author Aaron Zhu
* @date 2022-02-02
*/
public class LowBit {
public static void main(String[] args) {
// lowbit( 172 ) = lowbit( 0b10101100 ) = 0b100 = 4
Integer num1 = 172;
// 方式1
Integer result1 = num1 & (~num1+1);
// 方式2
Integer result2 = num1 & -num1;

System.out.println("num1: " + Integer.toBinaryString(num1) + " -->> " + num1);
System.out.println("num2: " + Integer.toBinaryString(result1) + " -->> " + result1);
System.out.println("num3: " + Integer.toBinaryString(result2) + " -->> " + result2);
}
}

测试结果如下所示,符合预期

figure 1.jpeg

Fenwick Tree树状数组

基本原理

假设存在这样的一个数组:1,3,2,1,0,6,8,4,9,1,4。我们按照同一层两两向上归并求和的思路建立Fenwick Tree树状数组,如下所示。例如第一层的1、3合并得到第二层的4;然后每一列只保留最顶层的元素,例如第2列4、3只保留上面的4。这里为了便于观察,在建立Fenwick Tree树状数组过程中,将需要丢弃的中间计算结果标记红底,将需要保留下来的元素标记为绿底

figure 2.jpeg

则最终树状数组的如下所示。可以看到其逻辑上虽然是一棵树,但物理上却可以通过数组来进行表示。这也是树状数组名称的由来

figure 3.jpeg

对于树状数组bit而言,我们规定其索引下标从1开始。则树状数组中的元素值如下

1
2
3
4
5
bit[1]=1, bit[2]=4, bit[3]=2
bit[4]=7, bit[5]=0, bit[6]=6
bit[7]=8, bit[8]=25, bit[9]=9
bit[10]=10
bit[11]=4

从上不难看出,对于树状数组中的元素而言,其是原数组a中部分元素的和。需要再次提醒:原数组的索引是从0开始的,而树状数组的元素则是从1位置开始存储的。所以原数组的元素索引要比相应的树状数组的元素索引小1

1
2
3
4
5
6
bit[1] = a[0] = 1
bit[2] = a[0]+a[1] = 1+3 = 4
bit[3] = a[2] = 2
bit[4] = a[0]+a[1]+a[2]+a[3] = 1+3+2+1 = 7
bit[5] = a[4] = 0
...

前面提到逻辑上数组bit是一颗树,故bit数组的元素值是其各子节点的元素值、及其所对应的原数组元素之和。例如

1
2
3
4
5
bit[2] = bit[1]+a[1] = 1+3 = 4
bit[4] = bit[3]+bit[2]+a[3] = 2+4+1 = 7
bit[8] = bit[7]+bit[6]+bit[4]+a[7] = 8+6+7+4 = 25
bit[10] = bit[9]+a[9] = 9+1 = 10
...

单点更新

如果期望对原数组a[1]进行修改,则首先需要更新树状数组相应的元素,即bit[2]。与此同时还需要更新所有的父节点:bit[4]、bit[8]。同理,修改a[4]需要更新树状数组bit[5]、bit[6]、bit[8];修改a[9]需要更新树状数组bit[10]

现在问题就来了,如何找到树状数组bit某个节点的父节点呢?这里以bit[5]及其父节点bit[6]、bit[8]的索引为例,将其转换为二进制

1
2
3
5 = 0101
6 = 0110 = 0101 + 1
8 = 1000 = 0110 + 10

从上不难看出,子节点与父节点索引的计算方式为

1
parentIndex = childIndex + lowbit(childIndex)

例如5的二进制为0101,其lowbit(5)=lowbit(0b0101)=1。则索引为5的树状节点,其父节点的索引为 5+1 = 6

前缀和

从上图不难可以看出:

1
2
3
bit[4] = a[0]+a[1]+a[2]+a[3] = 1+3+2+1 = 7
bit[6] = a[4]+a[5] = 0+6 = 6
bit[7] = a[6] = 8

那如果期望计算原数组的前缀和。例如a[0]~a[6]的和,则只需计算bit[7]、bit[6]、bit[4]三者之和。现在问题就来了,如何获取树状数组的索引下标呢?首先第一个下标肯定是原数组a[6]元素所对应树状数组的索引,即bit[7]。而剩余的6、4怎么得来呢?其实很简单,我们将其转换为二进制

1
2
3
7 = 0111
6 = 0110 = 0111 - 1
4 = 0100 = 0110 - 10

其实不难看出,当前节点与下一个节点索引的计算方式为

1
nextIndex = currentIndex + lowbit(currentIndex)

例如7的二进制为0111,其lowbit(7)=lowbit(0b0111)=1。则下一个节点索引为 7-1=6
同理6的二进制为0110,其lowbit(6)=lowbit(0b0110)=0b10=2。则下一个节点索引为 6-2=4
同理4的二进制为0100,其lowbit(4)=lowbit(0b0100)=0b100=4。则下一个节点索引为 4-4=0。但由于树状数组的索引是从1开始的,故索引0是无效的

Java实现

至此可以看到通过Fenwick Tree树状数组,可以高效地进行单点修改、前缀和。而利用前缀和则可进一步实现区间查询、单点查询。基于Java的实现如下所示

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**
* 树状数组: 单点修改、前缀和、区间查询、单点查询
* @author Aaron Zhu
* @date 2022-02-02
*/
public class FenwickTree1 {
/**
* 原数组
*/
private int[] array;

/**
* 树状数组
*/
private int[] bit;

public FenwickTree1(int[] array) {
this.array = new int[ array.length ];
this.bit = new int[ array.length+1 ];

for(int i=0; i<array.length; i++) {
update(i, array[i]);
}
}

/**
* [单点修改]: 将原数组index处元素修改为num
* @param index 原数组的索引下标
* @param num 绝对值
*/
public void update(int index, int num) {
// 计算增量
int delta = num - array[index];
// 修改原数组
array[index] = num;
// 树状数组索引从1开始
int bitIndex = index+1;
while ( bitIndex < bit.length ) {
bit[bitIndex] += delta;
// 计算树状数组中父节点的索引位置
bitIndex = bitIndex + lowBit(bitIndex);
}
}

/**
* [前缀和]: 计算原数组中至第index项的前缀和
* @param index 原数组的索引下标
* @return
*/
public int getPrefixSum(int index) {
int sum = 0;
// 树状数组索引从1开始
int bitIndex = index+1;
while (bitIndex>0) {
sum += bit[ bitIndex ];
// 计算树状数组的下一个索引位置
bitIndex = bitIndex - lowBit(bitIndex);
}
return sum;
}

/**
* [区间查询]: 计算原数组中第startIndex项至第endIndex项的区间和
* @param startIndex 原数组的区间起始索引下标
* @param endIndex 原数组的区间结束索引下标
* @return
*/
public int getRangeSum(int startIndex, int endIndex) {
int prefixUSum2 = getPrefixSum(endIndex);
// 从原数组第0项开始, 故相当于直接计算前缀和
if( startIndex==0 ) {
return prefixUSum2;
}

int prefixUSum1 = getPrefixSum(startIndex-1);
int rangSum = prefixUSum2 - prefixUSum1;
return rangSum;
}

/**
* [单点查询]: 查询原数组的元素
* @param index 原数组的索引下标
* @return
*/
public int getElement(int index) {
return getRangeSum(index, index);
}

/**
* 非负整数n在二进制表示下最低位1及其后面的0所构成的数值
* @param n
* @return
*/
private int lowBit(int n) {
return n & -n;
}
}

拓展

区间修改、单点查询

所谓区间修改是指对指定区间范围内的每一个元素均增加指定的增量。前面提到Fenwick Tree树状数组支持单点修改,那进行区间修改自然也是可以的。直接将区间修改转换为若干次的单点修改。但此时时间复杂度就为线性对数时间了。那有没有办法将区间修改的时间复杂度降到对数级别呢,答案自然是可以的

这里引入差分数组d,用于计算原数组的差分结果。可以看到对原数组[L,R]区间增加num,反映在差分数组d上,只需对差分数组d进行两次单点修改即可。具体地,对d[L]增加num、d[R+1]减少num即可

figure 4.jpeg

而如果期望对原数组进行单点查询,则只需计算差分数组的前缀和即可。例如:

1
2
3
4
5
6
7
a[3] = d[0] + d[1] + d[2] + d[3]
= x0+(x1-x0)+(x2-x1+num)+(x3-x2)
= x3 + num

a[5] = d[0] + d[1] + d[2] + d[3] + d[4] + d[5]
= x0+(x1-x0)+(x2-x1+num)+(x3-x2)+(x4-x3)+(x5-x4-num)
= x5

换言之,如果期望进行区间修改、单点查询。只需先将原数组转换为差分数组,再对差分数组建立Fenwick Tree树状数组即可。基于Java的实现如下所示

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/**
* 树状数组: 区间修改、单点查询
* @author Aaron Zhu
* @date 2022-02-02
*/
public class FenwickTree2 {
/**
* 原数组
*/
private int[] array;

/**
* 差分数组: 对原数组进行差分
*/
private int[] delta;

/**
* 差分数组的树状数组
*/
private int[] bit;

public FenwickTree2(int[] array) {
this.array = array;

// 根据原数组计算差分数组
delta = new int[ array.length ];
for(int i=0; i<array.length; i++) {
if ( i==0 ) {
delta[0] = array[0];
} else {
delta[i] = array[i] - array[i-1];
}
}

// 将 差分数组 转换为 树状数组
bit = new int[ delta.length+1 ];
for(int i=0; i<delta.length; i++) {
// 初始化树状数组, 则变化量就是差分数组的元素本身
update(i, delta[i]);
}
}

/**
* [区间修改]: 对原数组中第startIndex项至第endIndex项均增加变化量num
* @param startIndex
* @param endIndex
* @param num
*/
public void updateRange(int startIndex, int endIndex, int num) {
// 差分数组的变化相当于: add(l, d), add(r+1, -d)

// 差分数组的第startIndex项元素增加变化量 num
update(startIndex, num);
// 当endIndex不是最后一个元素
if( endIndex < delta.length-1 ) {
// 差分数组的第endIndex+1项元素增加变化量 -num
update(endIndex+1, -num);
}
}

/**
* [单点查询]: 查询原数组的元素
* @param index 原数组的索引下标
* @return
*/
public int getElement(int index) {
int element = 0;
// 树状数组索引从1开始
int bitIndex = index+1;
while (bitIndex>0) {
element += bit[ bitIndex ];
// 计算树状数组的下一个索引位置
bitIndex = bitIndex - lowBit(bitIndex);
}
return element;
}

/**
* 差分数组index处的元素在增加变化量num后, 对树状数组进行更新
* @param index 原数组的索引下标
* @param num 变化量
*/
private void update(int index, int num) {
// 树状数组索引从1开始
int bitIndex = index+1;
while ( bitIndex < bit.length ) {
bit[bitIndex] += num;
// 计算树状数组中父节点的索引位置
bitIndex = bitIndex + lowBit(bitIndex);
}
}

/**
* 非负整数n在二进制表示下最低位1及其后面的0所构成的数值
* @param n
* @return
*/
private int lowBit(int n) {
return n & -n;
}
}

区间修改、前缀和、区间查询

如前文所述,原数组的区间修改可借助于差分数组进行实现

figure 5.jpeg

结合上图上文易知

1
2
3
4
5
a[0] = d[0]
a[1] = d[0]+d[1]
a[2] = d[0]+d[1]+d[2]
a[3] = d[0]+d[1]+d[2]+d[3]
...

那如何实现原数组的前缀和呢?比如计算a[0]~a[3]之和,则可知

1
2
sum = a[0]+a[1]+a[2]+a[3]
= 4*d[0] + 3*d[1] + 2*d[2] + d[3]

但事实上这个计算非常不便,我们对sum进行可视化。具体地,将差分元素d[x]表示为:长为元素值d[x]、宽为1的矩形,如下图所示。可以看到sum值其实就是绿色部分的面积

figure 6.jpeg

既然直接计算绿色部分的面积不便,我们转换个思路。用外部大矩形的面积减去蓝色部分的面积即可

figure 7.jpeg

至此可以发现,前半部分实际上就是差分数组的前缀和;而对于后半部分,则可先建立一个元素值为(i+1)*d[i]的辅助数组,然后通过计算该辅助数组的前缀和进行实现。即:

1
2
# 这里 i 为原数组的下标索引
原数组的前缀和 = (i+2) * 差分数组的前缀和 - 辅助数组的前缀和

既然计算前缀和已经实现,则可进一步地进行区间查询。这里给出Java下的实现

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
/**
* 树状数组: 区间修改、前缀和、区间查询
* @author Aaron Zhu
* @date 2022-02-02
*/
public class FenwickTree3 {
/**
* 原数组
*/
private int[] array;

/**
* 差分数组: 对原数组进行差分
* 元素记为D[0]、D[1]、D[2]...D[n_1]
*/
private int[] delta;

/**
* 差分数组的树状数组
*/
private int[] bit1;

/**
* 辅助数组: 存储的元素值为 (i+1) * D[i]
*/
private int[] temp;

/**
* 辅助数组的树状数组
*/
private int[] bit2;

public FenwickTree3(int[] array) {
this.array = array;

// 根据 原数组 计算 差分数组
delta = new int[ array.length ];
for(int i=0; i<array.length; i++) {
if ( i==0 ) {
delta[0] = array[0];
} else {
delta[i] = array[i] - array[i-1];
}
}

// 根据 差分数组 计算 辅助数组
temp = new int[ delta.length ];
for(int i=0; i<delta.length; i++) {
temp[i] = (i+1) * delta[i];
}

// 将 差分数组 转换为 树状数组
bit1 = new int[ delta.length+1 ];
for(int i=0; i<delta.length; i++) {
// 初始化树状数组, 则变化量就是差分数组的元素本身
update(i, delta[i], bit1);
}

// 将 辅助数组 转换为 树状数组
bit2 = new int[ temp.length+1 ];
for(int i=0; i<temp.length; i++) {
// 初始化树状数组, 则变化量就是辅助数组的元素本身
update(i, temp[i], bit2);
}
}

/**
* [区间修改]: 对原数组中第startIndex项至第endIndex项均增加变化量num
* @param startIndex
* @param endIndex
* @param num
*/
public void updateRange(int startIndex, int endIndex, int num) {
// 差分数组的变化相当于: add(l, d), add(r+1, -d)

// 差分数组的第startIndex项元素增加变化量 num
update(startIndex, num, bit1);
// 当endIndex不是最后一个元素
if( endIndex < delta.length-1 ) {
// 差分数组的第endIndex+1项元素增加变化量 -num
update(endIndex+1, -num, bit1);
}

// 辅助数组的变化相当于: add(l, (l+1)*d), add(r+1, -(r+2)*d)

// 辅助数组的第startIndex项元素增加变化量 (startIndex+1)*num
update(startIndex, (startIndex+1)*num, bit2);
// 当endIndex不是最后一个元素
if( endIndex < temp.length-1 ) {
// 辅助数组的第endIndex+1项元素增加变化量 -(endIndex+2)*num
update(endIndex+1, -(endIndex+2)*num, bit2);
}
}

/**
* [前缀和]: 计算原数组中至第index项的前缀和
* @param index 原数组的索引下标
* @return
*/
public int getPrefixSum(int index) {
// 原数组的前缀和 = (i+2) * 差分数组的前缀和 - 辅助数组的前缀和

// 计算差分数组的前缀和
int deltaSum = 0;
// 树状数组索引从1开始
int bit1Index = index+1;
while (bit1Index>0) {
deltaSum += bit1[ bit1Index ];
// 计算树状数组的下一个索引位置
bit1Index = bit1Index - lowBit(bit1Index);
}

// 计算辅助数组的前缀和
int tempSum = 0;
// 树状数组索引从1开始
int bit2Index = index+1;
while (bit2Index>0) {
tempSum += bit2[ bit2Index ];
// 计算树状数组的下一个索引位置
bit2Index = bit2Index - lowBit(bit2Index);
}

int result = (index+2) * deltaSum - tempSum;
return result;
}

/**
* [区间查询]: 计算原数组中第startIndex项至第endIndex项的区间和
* @param startIndex 原数组的区间起始索引下标
* @param endIndex 原数组的区间结束索引下标
* @return
*/
public int getRangeSum(int startIndex, int endIndex) {
int prefixUSum2 = getPrefixSum(endIndex);
// 从原数组第0项开始, 故相当于直接计算前缀和
if( startIndex==0 ) {
return prefixUSum2;
}

int prefixUSum1 = getPrefixSum(startIndex-1);
int rangSum = prefixUSum2 - prefixUSum1;
return rangSum;
}

/**
* 数组index处的元素在增加变化量num后, 对树状数组bit进行更新
* @param index 原数组的索引下标
* @param num 变化量
* @param bit 树状数组
*/
private void update(int index, int num, int[] bit) {
// 树状数组索引从1开始
int bitIndex = index+1;
while ( bitIndex < bit.length ) {
bit[bitIndex] += num;
// 计算树状数组中父节点的索引位置
bitIndex = bitIndex + lowBit(bitIndex);
}
}

/**
* 非负整数n在二进制表示下最低位1及其后面的0所构成的数值
* @param n
* @return
*/
private int lowBit(int n) {
return n & -n;
}
}

应用

剑指Offer(第2版): 51. 数组中的逆序对

这里以经典例题为例展开介绍:LeetCode 的剑指Offer(第2版)题单中的第51题——数组中的逆序对

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数

示例 1:
输入:[7,5,6,4]
输出:5

对于本题而言最朴素的思路就是暴力遍历数组进行统计,但此举的时间复杂度数平方级别,显然不可接受

现在假设数组a为:2、3、9、7、6。我们依次遍历该数组统计重复元素出现的次数,并将统计结果保存到数组c中。其中索引为元素的值,值为次数。当准备遍历原数组的a[3]元素7时,统计结果数组c则如下所示

1
2
3
// 次数统计结果数组 c
index -->> 2 3 6 7 9
count -->> 1 1 0 0 1

可以看到此时c[0]到c[7]之和为2。换句话说,对于原数组的第4个元素7而言,其与前面的3个元素依次比较,存在2个顺序对:(2,7)、(3,7)。则逆序对的数量为:3 - 2 = 1

同理,当准备遍历原数组的a[4]元素6时,统计结果数组c则如下所示。可以看到此时c[0]到c[6]之和为2。换句话说,对于原数组的第5个元素6而言,其与前面的4个元素依次比较,存在2个顺序对:(2,6)、(3,6)。则逆序对的数量为:4 - 2 = 2

1
2
3
// 次数统计结果数组 c
index -->> 2 3 6 7 9
count -->> 1 1 0 1 1

最终对于数组a而言,其逆序对的数量共计为3。不难看出我们只需在遍历原数组过程中,计算统计结果数组c的前缀和即可。而计算统计结果数组c的前缀和则可通过Fenwick Tree树状数组来提高效率

但其实这里中还有一个小问题需要进行处理。前面提到统计结果数组的索引是源自原数组的元素值。比如假设原数组为:2、996、3。则统计数组c需要长度为997的数组空间,但实际上只会使用c[2]、c[3]、c[996]这三个元素位置。特别是如果原数组中存在一个非常大的数,显然这样会造成内存空间的极大浪费,且内存空间的利用率非常低。故我们需要对原数组的元素值进行离散化处理。就本题而言,我们需要的是元素之间的相对关系而非绝对值。一个非常简单的处理思路就是对原数组的N个元素进行去重、排序,用排序的顺序代替原来的元素值。这样就可将无限空间的元素值映射到1~N的排名范围内,这样统计数组c就只需长度为N+1的数组空间

例如原数组:112、996、203。排序后为:112、203、996,即112排名第1、203排名第2、996排名第3。故原数组离散化的结果即为:1、3、2。至此本题的思路、解法就完全清晰明了了,具体实现如下

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**
* 剑指Offer(第2版): 51. 数组中的逆序对
* @author Aaron Zhu
* @date 2022-2-1
*/
class Solution {
/**
* key: 原始数组的元素值; value: 排名值(相对大小关系, 其中1是最小的)
*/
private Map<Integer, Integer> rankMap;

public int reversePairs(int[] nums) {
int result = 0;
if( nums==null || nums.length==0 ) {
return result;
}

// 离散化处理
buildRankMap(nums);

FenwickTree fenwickTree = new FenwickTree( nums.length+1 );

for(int i=0; i<nums.length; i++) {
// 获取离散化处理后的值
int rankNum = rankMap.get(nums[i]);

// 原数组已经遍历完成的个数
int allNum = i;
// 计算顺序对的数量(含相等情形)
int pairNum = fenwickTree.getPrefixSum( rankNum );
// 逆序对的个数 = 原数组已经遍历完成的个数 - 顺序对的个数
int reversePairNum = allNum - pairNum;

// 计数加1, 故对树状数组索引为rankNum进行加1
fenwickTree.update(rankNum,1);
result += reversePairNum;
}

return result;
}

private void buildRankMap(int[] nums) {
// 对原数组进行去重排序, 已获取相对关系
int[] temp = Arrays.stream(nums)
.distinct()
.sorted()
.toArray();

rankMap = new HashMap<>();
for(int i=0; i<temp.length; i++) {
// key: 原始数组的元素值; value: 排名值(相对大小关系, 其中1是最小的)
rankMap.put(temp[i], i+1);
}
}

public static class FenwickTree {

private int[] bit;

public FenwickTree(int size) {
bit = new int[size];
}

/**
* 计算前缀和
* @param index
* @return
*/
public int getPrefixSum(int index) {
int sum = 0;
while (index>0) {
sum += bit[index];
index = index - lowbit(index);
}
return sum;
}

/**
* 单点增量更新
* @param index
* @param delta
*/
public void update(int index, int delta) {
while (index<bit.length) {
bit[index] += delta;
index = index + lowbit(index);
}
}

private int lowbit(int num) {
return num & -num ;
}
}
}
0%