「简记」树状数组

发表于 Artalk： loading...
binary indexed tree

原理分析部分参考 树状数组-耀凯

代码实现

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

    public BinaryIndexedTree(int[] nums) {
        this.n =  nums.length;
        this.bit = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            update(i, nums[i - 1]);
        }
    }

    public int lowBit(int x) {
        return x & -x;
    }
    // pos位置的元素值加u
    void update(int pos, int u) {
        for (int i = pos; i <= n; i += lowBit(i)) {
            bit[i] += u;
        }
    }

    // 返回 [1,pos]的元素和
    int query(int pos) {
        int ans = 0;
        for (int i = pos; i > 0; i -= lowBit(i)) {
            ans += bit[i];
        }
        return ans;
    }
}

例题

307. 区域和检索 - 数组可修改

给你一个数组 nums ，请你完成两类查询。

  1. 其中一类查询要求 更新 数组 nums 下标对应的值
  2. 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right

示例

1
2
3
4
5
6
7
8
9
10
11
输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

代码实现

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
class NumArray {
    // 单点修改，区间查询
    // 数状数组
    int[] bit, nums;
    int n;
    int lowbit(int x) { return x & -x; }
    void add(int pos, int u) {
        for (int i = pos; i <= n; i += lowbit(i)) {
            bit[i] += u;
        }
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            ans += bit[i];
        }
        return ans;
    }
    public NumArray(int[] _nums) {
        nums = _nums;
        this.n = _nums.length;
        this.bit = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            add(i + 1, nums[i]);
        }
    }
    
    public void update(int index, int val) {
        this.add(index + 1, val - nums[index]);
        nums[index] = val;
    }
    
    public int sumRange(int left, int right) {
        return query(right + 1) - query(left);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */

📔博文图谱

提及本博文的链接