首页

树状数组可以解决的问题：多次单点修改后多次求区间和

前缀数组可以解决的问题：数组不变，多次求区间和

差分数组可以解决的问题：多次整体修改某个区间，求全部数组和

线段树可以解决的问题：多次整体修改某个区间后多次求区间和

参考

307. 区域和检索 - 数组可修改 - 力扣（LeetCode）

树状数组 详解树状数组, 包含更新查询图解, 秒懂lowbit含义

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
class TreeArray {
    int[] tree;
    int[] nums;
    public TreeArray(int[] _nums) {
        tree = new int[_nums.length + 1];  // 树状数组的下标从1开始
        this.nums = _nums;
        for (int i = 0; i < nums.length; i++) {
            int idx = i + 1;
            tree[idx] += nums[i];
            int idx2 = idx + (idx & -idx); // 注意运算符优先级
            if (idx2 <= nums.length){
                tree[idx2] += tree[idx];
            }
        }
    }
    // O(nlog(n))的写法
    public TreeArray(int[] _nums) {
        tree = new int[_nums.length + 1];  // 树状数组的下标从1开始
        this.nums = new int[_nums.length];
        for (int i = 0; i < _nums.length; i++) {
            update(i, _nums[i]);
        }
    }
    
    /*
    * 更新nums[idx]为newValue
    * */
    public void update(int idx, int newValue) {
        int delta = newValue - nums[idx];
        nums[idx] = newValue;
        idx += 1;
        while (idx <= nums.length) {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }
    
    /*
    * 查询[l,r]之间的子数组之和
    * */
    public int query(int l, int r) {
        return preSum(r) - preSum(l - 1);
    }
    
    
    /*
    * 查询[0,idx]之间的子数组之和
    * */
    public int preSum(int idx) {
        int s = 0;
        idx += 1;
        while (idx > 0){
            s += tree[idx];
            idx -= idx & -idx;
        }
        return s;
    }
}

统计频率和的树状数组或归并排序：

327. 区间和的个数 - 力扣（LeetCode）

493. 翻转对 - 力扣（LeetCode）

315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）

307. 区域和检索 - 数组可修改 - 力扣（LeetCode）