树状数组

学习数据结构与算法
2021-05-17 14:29 · 阅读时长4分钟
小课

树状数组和线段树一样,也是用来维护区间信息的,不过实现起来比线段树更加简洁,但是没有线段树灵活、强大。树状数组,很明显就是说数组的逻辑结构是树形的,但是这个树形数组和之前提到过的结构都不太一样,它的子节点和父节点的位置并不是2n,2n+1,2n+2等这种关系,而是通过一个特殊的函数lowbit来获取,lowbit函数实际功能是取当前数字二进制形式从右往左直到遇到1为止所表示的值,比如说十进制6,它的二进制表示为110,lowbit要取的值就是10,也就是2。它可以通过以下方式实现

public int lowBit(int val) {
    return val & -val;
}

并且在查询、和更新树状数组时,使用方式还不一样,在更新时,通过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