树状数组
收录于
学习数据结构与算法
2021-05-17 14:29 · 阅读时长4分钟
树状数组和线段树一样，也是用来维护区间信息的，不过实现起来比线段树更加简洁，但是没有线段树灵活、强大。树状数组，很明显就是说数组的逻辑结构是树形的，但是这个树形数组和之前提到过的结构都不太一样，它的子节点和父节点的位置并不是2n，2n+1，2n+2等这种关系，而是通过一个特殊的函数lowbit来获取，lowbit函数实际功能是取当前数字二进制形式从右往左直到遇到1为止所表示的值，比如说十进制6，它的二进制表示为110，lowbit要取的值就是10，也就是2。它可以通过以下方式实现
并且在查询、和更新树状数组时，使用方式还不一样，在更新时，通过parent = child + lowbit(child) 来获取父节点的位置，而在查询时，通过parent = child - lowbit(child)来获取父节点位置。
下面以数组arr=[1, 2, 3, 4, 5, 6, 7, 8]求区间和为例，看看具体这个树状数组是什么样的。
树状数组实现起来比较简单，主要是理解更新和查询时树的结构。
1class FenwickTree {
2
3 int[] sum;
4 int[] num;
5
6 public FenwickTree(int[] nums) {
7 num = new int[nums.length];
8 sum = new int[nums.length + 1];
9 for (int i = 0; i < nums.length; i++) {
10 update(i, nums[i]);
11 }
12 }
13
14 /**
15 * 更新节点和树状数组
16 *
17 * @param i 要更新的元素下标
18 * @param val 更新后的值
19 */
20 public void update(int i, int val) {
21 int origin = num[i];
22 num[i] = val;
23 i++;
24 /**
25 * 不断更新父节点
26 */
27 while (i < sum.length) {
28 sum[i] = sum[i] - origin + val;
29 i = i + lowBit(i);
30 }
31 }
32
33 /**
34 * 查询
35 *
36 * @param i 要查询区间的结束位置
37 * @return 区间元素之和
38 */
39 public int query(int i) {
40 i++;
41 int res = 0;
42 /**
43 * 不断累加父节点的值
44 */
45 while (i > 0) {
46 res += sum[i];
47 i = i - lowBit(i);
48 }
49 return res;
50 }
51
52 /**
53 * 查询
54 *
55 * @param i 要查询区间的起始位置
56 * @param j 要查询区间的结束位置
57 * @return
58 */
59 public int query(int i, int j) {
60 return query(j) - query(i - 1);
61 }
62
63 public int lowBit(int val) {
64 return val & -val;
65 }
66}
67
68public class Main {
69
70 public static void main(String[] args) {
71 int[] arr = {1, 3, -1, 2, 5};
72 FenwickTree tree = new FenwickTree(arr);
73 System.out.println(tree.query(0, 3));
74 tree.update(2, 1);
75 System.out.println(tree.query(0, 3));
76 }
77}
78注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main
一般来说，能用树状数组来实现，就用树状数组来实现，因为树状数组实现简单，而且效率要比线段树高一些。
树状数组Fenwick TreeBinary Indexed Tree
1