Garden of Sinners
0%

BinaryIndexedTree

Posted on In

记录一下【树状数组】的个人模版。

BinaryIndexedTree主要功能是提供动态的O(logn)时间复杂度内计算前缀和。树状数组和线段树是不同的实现方法，树状数组的设计目的是为了更高效地计算前缀和，而线段树的设计目的是更高效的计算区间和，二者在如“和”这种简单计算上可以互相替代，毕竟计算前缀和就能计算区间和，计算区间和就包括计算前缀和。但实际上，线段树面向的不仅是区间和的高效计算，它的分治法可以处理任何具有二段性的计算；而树状数组更多的是利用了加法和二进制的某些特性。

有人也许会问，什么时候需要用到这些高级数据结构。如果只是计算静态的前缀和，当然不需要引入这些；但是如果想要动态地去进行计算，数组中的元素发生更改时能够在O(logn)内计算出新的结果，那么这些高级数据结构便是必要的。

模版

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
public class BinaryIndexedTree {
    private int[] bits;

    public BinaryIndexedTree(int[] nums) {
        int n = nums.length;
        bits = new int[n+1];
        System.arraycopy(nums, 0, bits, 1, n);
        for (int i=1; i < n; i++) {
            int nxt = i + (i & (-i));
            if (nxt <= n)
                bits[nxt] += bits[i];
        }
    }

    public void update(int index, int delta) {
        int i = index + 1;
        while (i < bits.length) {
            bits[i] += delta;
            i += (i & -i);
        }
    }

    // [0, index)
    public int prefixSum(int index) {
        int i = index;
        int res = 0;
        while (i > 0) {
            res += bits[i];
            i -= (i & -i);
        }
        return res;
    }

    // [fromIndex, toIndex)
    public int rangeSum(int fromIndex, int toIndex) {
        return prefixSum(toIndex) - prefixSum(fromIndex);
    }
}

参考