树状数组

概念

树状数组（Fenwick Tree）是一种数组实现的树状结构，常用于解决前缀和问题。它能够在O(log n)的时间内进行单点更新与区间查询操作，特别适用于在动态变化的数组中进行频繁的前缀和查询和更新。

通常需要对输入数据进行离散化，因为数据通常是不连续，而数组要求索引连续

  • 操作
    • 单点修改：更改数组中一个元素的值
    • 区间查询：查询一个区间内所有元素的和

范围：[1, n];

例如：7（111）

单点修改：111 -> 1000

区间查询：111 -> 110 -> 100

前缀和模板

注意不能add(0, val)，无法跳出循环，因为lowbit(0) = 0

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
class FenwickTree {
    int[] tr;  // [1, n]
    public FenwickTree(int[] nums) {  // [0, n-1]
        this.tr = new int[nums.length+1];
        for (int i = 0; i < nums.length; i++) {
            add(i+1, nums[i]);
        }
    }
    public int lowbit(int x) {
        return x & (-x);
    }
    public void add(int i, int val) {
        while (i < tr.length) {
            tr[i] += val;
            i += lowbit(i);
        }
    }
    public int query(int i) {
        int res = 0;
        while (i > 0) {
            res += tr[i];
            i -= lowbit(i);
        }
        return res;
    }
}

前缀最大值模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class FenwickTree {
    int[] tr;
    public FenwickTree(int n) {
        this.tr = new int[n];
        Arrays.fill(tr, -1);
    }
    public int lowbit(int x) {
        return x & (-x);
    }
    public void add(int i, int val) {
        while (i < tr.length) {
            tr[i] = Math.max(tr[i], val);
            i += lowbit(i);
        }
    }
    public int query(int i) {
        int res = -1;
        while (i > 0) {
            res = Math.max(res, tr[i]);
            i -= lowbit(i);
        }
        return res;
    }
}

相关题解