七秒记忆
0%

树状数组

发表于 分类于

树状数组 或 二叉索引树 （Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和，区间和。

单点更新

1
2
3
4
5
6
void update(int x, int val) {
    while (x <= N) {
        bit[x] += val;
        x += lowbit(x);
    }
}

求最低位1

巧妙地利用了负数是以 补码 （反码 + 1）的形式存储，将原数字和它的补码 按位与 得到最低位的 1。

1
2
3
int lowbit(int x) {
    return x & -x;
}

求前缀和

1
2
3
4
5
6
7
8
int query(int x) {
    int ans = 0;
    while (x > 0) {
        ans += bit[x];
        x -= lowbit(x);
    }
    return ans;
}

求区间和

1
2
3
int query(int a, int b) {
    return query(b) - query(a - 1);
}

测试代码

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
package 数据结构;

public class BitTree {
    static int N;
    static int[] bit;

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5};
        N = nums.length;
        bit = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            update(i, nums[i - 1]);
        }
        System.out.println("前缀和：" + query(4));
        System.out.println("区间和：" + query(2, 4));
    }

    // 求前缀和
    public static int query(int x) {
        int ans = 0;
        while (x > 0) {
            ans += bit[x];
            x -= lowbit(x);
        }
        return ans;
    }

    // 求区间和
    public static int query(int a, int b) {
        return query(b) - query(a - 1);
    }

    // 单点更新
    public static void update(int x, int val) {
        while (x <= N) {
            bit[x] += val;
            x += lowbit(x);
        }
    }

    // 求最低位1
    public static int lowbit(int x) {
        return x & -x;
    }
}