稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

树状树组简介

树状数组,即Binary Indexed Tree,简单来理解就是用数组来表示一颗树,它的实际存储结构是数组,但元素之间的逻辑关系是树。通常用于解决区间问题和快速计算前缀和的问题。

区间查询和区间修改

在介绍树状数组之前,先来看一个问题,给定数组nums,长度为n,如何快速实现如下四种操作:

操作 参数 说明
单点查询 i 查询索引为i的元素值
区间查询 l, r 查询区间[l, r]内元素之和
单点修改 i 修改索引 为i的元素值
区间修改 l, r 修改区间[l, r]内的元素值,比如都加上一个数x

首先,肯定 可以想到朴素做法,简单的优化就是用前缀和(参考此文),可以做如下对比:

操作 方法 时间复杂度 方法 时间复杂度 方法 时间复杂度
单点查询 朴素做法 O(1) 前缀和 O(1) 差分数组 O(n)
区间查询 朴素做法 O(n) 前缀和 O(1) 差分数组 O(n)
单点修改 朴素做法 O(1) 前缀和 O(n) 差分数组 O(1)
区间修改 朴素做法 O(n) 前缀和 O(n) 差分数组 O(1)

可以看到基本的方法必然会有一种操作会达到O(n)复杂度。而用树状数组就可以区间相关的操作(区间查询和区间修改)都降到O(logn)。

注意:单点操作,可以视为区间操作的特例,比如区间查询i,可以视为区间查询[i, i]。

树状数组的思想

树状数组就是把原数组分成多个区间,用一个辅助数组来存储这些划分出来的区间的区间和。普通前缀和,对于区间查询 和单点查询 来说肯定 可以O(1)来完成,但对于单点修改,比如要修改nums[i]的值,这会影响到包含nums[i]的所有的区间和,因此会是O(n)的复杂度。树状数组因为预先划分了一些区间,能能够保证受nums[i]影响的区间只有O(logn)个,因此单点修改对于树状数组的复杂度只会是O(logn)。

树状数组是一个辅助数组tree[],长度是原数组长度n+1,区间划分的原则是从[1,n]中的每一个下标i,存储的是一个区间和,这个区间是(i-lowbit(i),i],注意区间是左开右闭。这个lowbit是一个函数取的是索引i的最左一个1所代表的数字,比如索引4,其lowbit(4) = (0b100)2=4,所以tree[4]存储的是(0,4]这个区间的区间和;而5,lowbit(5)=(0b101)2=1,所以tree[5]只存它自己。

这样划分区间后,对于单点修改,只需要把包含影响的元素的区间更新一遍就可以了。比如修改元素i,那么只需要把[i, i+lowbit(i)]的元素更新一下就可以了。

对于区间查询,区间查询用前缀和可以做到O(1),因此问题的关键在于利用划分的区间和区间和来找到前缀和。区间划分大小为lowbit(i),tree[i]存储的是(i-lowbit(i), i]的和,那么,如果令j=i-lowbit(i),那么tree[j]就是(j-lowbit(j),j]的和,这样一直到索引0,就找到了到i的前缀和了。由此可以看出用下标索引lowbit来划分区间可以非常巧妙的分治单点修改和区间查询的问题,使得复杂度都降为O(logn)。

lowbit

区间划分最为精妙 的就是这个lowbit,它是能保证tree中所有的查询和修改都能在O(logn)时间内完成。它的作用是取索引二进制形式的最后一个1所代表的数字。它的实现并不复杂,用一点位运算的技巧就可以了,位运算技巧可以参考文章

1
2
3
private static int lowbit(int i) {
    return i & -i;
}

细心的你肯定可以发现,对于奇数索引lowbit肯定是1,所以tree中奇数索引存储的都是原数组的元素,只有偶数索引存储的才是区间之和。

基础树状数组的实现

基于前面的原理,可以实现基础版本的树状数组,基础版本的意思是,对于单点修改和区间查询两个操作可以实现O(logn)复杂度的支持。

实现细节需要注意,树状数组是一个辅助数组tree,它的长度是原数组长度加1,索引为0的是不使用的,仅[1, n]是有效数据。

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
/**
 * The Binary Indexed Tree.
 */
public class BIT {
    // The original array, which is not really necessary.
    private int[] nums;

    // the size of the Binary Indexed array, size = n + 1, n is the length of original array.
    private int size;

    // The Binary Indexed Array, valid data are in [1, size), where size = n + 1
    // Original array element [i] is mapped to [i + 1] in the tree.
    private int[] tree;

    public BIT(int[] nums) {
        this.nums = nums;
        size = nums.length + 1;

        tree = new int[size];
        for (int i = 0; i < size - 1; i++) {
            add(i + 1, nums[i]);
        }
    }

    private static int lowbit(int i) {
        return i & -i;
    }

    // Update array element [i] to val
    // Meaning set nums[i] to val, but it is easier to maintain tree with delta
    // nums[i] = val, is the same to nums[i] = nums[i] + (val - nums[i]), where val - nums[i]
    // is the delta.
    // So we add affected items in tree with the delta.
    public void update(int i, int val) {
        add(i + 1, val - nums[i]);
        nums[i] = val;
    }

    private void add(int i, int x) {
        for (int j = i; j < size; j += lowbit(j)) {
            tree[j] += x;
        }
    }

    // Query the regional sum in [l, r]
    public int query(int l, int r) {
        return preSum(r + 1) - preSum(l);
    }

    // Get the preSum up to i inclusive.
    private int preSum(int i) {
        int sum = 0;
        for (int j = i; j > 0; j -= lowbit(j)) {
            sum += tree[j];
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        BIT bit = new BIT(a);

        System.out.println("3 = " + bit.query(0, 1));
        System.out.println("18 = " + bit.query(2, 5));

        bit.update(3, 5);
        System.out.println("3 = " + bit.query(0, 1));
        System.out.println("19 = " + bit.query(2, 5));
    }
}

典型题目

题目 题解 说明
题解
题解
题解
题解
题解
题解

参考资料

Comments