BinaryIndexedTree求解指定范围和

BinaryIndexedTree算法示例

Posted by Jeremy Song on 2022-07-23
Estimated Reading Time 2 Minutes
Words 498 In Total
Viewed Times

简介

树状数组或二叉索引树 Binary Indexed Tree,又以其发明者命名为 Fenwick树。其初衷是解决数据压缩里的累积频率的计算问题,现多用于高效计算数列的前缀和, 区间和。

代码实现

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
import java.util.Arrays;

public class BinaryIndexedTree {
int N;
int[] tree;
int[] input;

public BinaryIndexedTree(int[] input) {
this.input = input;
this.N = this.input.length;
this.tree = new int[treeSize()];
init();
}

/**
* 计算构造Binary Indexed Tree的一维数组大小
*
* @return
*/
int treeSize() {
int size = 1;
while (size < N) size <<= 1;
return size + 1; // +1是因为indexed tree的下标从1开始,0为无效的位
}

/**
* 初始化构造Binary Indexed Tree
*/
void init() {
// indexed tree下标从0开始,并且0位无效
for (int i = 1; i <= input.length; i++) update(i, input[i - 1]);
}

/**
* 更新指定位置的数值
*
* @param index Binary Indexed Tree的元素索引。即,输入数组的的索引+1。如果输入数组的索引从1开始有效,则可以直接使用其索引。<br/>
* 索引从1开始
* @param abs 指定位置的变更值=修改后的值-变更前的值
*/
void update(int index, int abs) {
while (index < tree.length) {
tree[index] += abs;
index += lowBit(index);
}
}

/**
* 计算前N项和,index从1开始计数
*/
int sum(int index) {
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= lowBit(index);
}
return sum;
}

/**
* 计算a到b的和(包含a和b)<br/>
* a和b均从0开始
*/
int between(int a, int b) {
// 转换成Binary Indexed Tree下标
int from = Math.min(a, b) + 1;
int to = Math.max(a, b) + 1;
return sum(to) - sum(from - 1); // 包含b
}

/**
* 计算低位值
*/
int lowBit(int index) {
return index & (-index);
}

// test code below

public static void main(String[] args) {
int[] input = new int[10];
Arrays.fill(input, 1);
BinaryIndexedTree bit = new BinaryIndexedTree(input);

bit.update(4, 1);
bit.update(9, 10);

System.out.println(bit.tree.length);
System.out.println("==============");
System.out.println(bit.between(1, 2));
System.out.println(bit.between(3, 5));
System.out.println(bit.between(3, 9));
System.out.println(bit.between(0, 9));
}
}

欢迎关注我的公众号 须弥零一,跟我一起学习IT知识。


如果您喜欢此博客或发现它对您有用,则欢迎对此发表评论。 也欢迎您共享此博客,以便更多人可以参与。 如果博客中使用的图像侵犯了您的版权,请与作者联系以将其删除。 谢谢 !