树状数组

简介

树状数组（Binary Indexed Tree，BIT）是一种用于高效处理前缀和的数据结构，支持以下操作：

  1. 单点更新：将某个位置的值增加或减少。
  2. 前缀查询：查询某个位置的前缀和（也可以是其他的二元运算，如异或、最大/最小值）。

树状数组的核心思想是通过二进制位操作来高效地维护前缀和。它的时间复杂度为 O(log n)，适用于动态查询和更新场景。

树状数组的下标0是无效的，从1开始计算，以下文字中的原数组的下标也从1开始计算。树状数组中元素tree[i]的含义是：从原数组nums[i]开始向左数lowbit个元素，这些元素的和。例如tree[14]表示nums[13]+nums[14]。

基本操作

以最基本的单点更新，求前缀和为例：

  1. lowbit 操作：提取一个数的最低位的 1。

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

  2. 单点更新：将某个位置的值增加或减少。

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

  3. 前缀查询：查询某个位置的前缀和。

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

  4. 区间和查询：如果要求某个区间[l, r]的区间和，可以利用前缀和的思想，两次query分别求出[0,r]的前缀和以及[0,l-1]的区间和，作差即可，不影响复杂度。

整体模板

以树状数组维护前缀最大值为例。

  1. 其中最大值操作可以换成其他二元运算，如sum，异或；
  2. 注意树状数组中下标0无效，因此size比原数组大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
class BIT {
    int n;
    int[] tree;

    BIT(int _n){
        this.n = _n + 1;
        this.tree = new int[n];
    }

    static int lowbit(int x){
        return x & (-x);
    }

    public int query(int x){
        ++x;
        int ret = 0;
        while(x > 0){
            int lb = lowbit(x);
            ret = Math.max(ret, tree[x]);
            x -= lb;
        }
        return ret;
    }

    public void update(int x, int val){
        ++x;
        while(x < n){
            int lb = lowbit(x);
            tree[x] = Math.max(tree[x], val);
            x += lb;
        }
    }
}

树状数组求区间最值

与求区间和不同，假设现在树状数组维护的是前缀最大值。在单点修改时，如果把nums[8]改小了，那么如果tree[8]保存的最大值正好就是nums[8]，那么tree[8]要由tree[7], tree[6], tree[4]中的某个数取代。因此在update方法中， 不能这样简单地写：tree[idx] = max(tree[idx], val);正确的写法在下方模板中：

1
2
3
4
5
6
7
8
9
10
11
12
// 修改下标为idx的数为val
void update(int idx, int val) {
	nums[idx] = val;
    tree[idx] = val;
    while (idx <= n) {
    	int lx = lowbit(idx);
    	for (int i = 1; i < lx; i <<= 1) {
    		tree[idx] = choose(tree[idx], tree[idx - i]);
    	}
    	idx += lx;
    }
}
完整模板（单点修改，区间查询最值）
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
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    // (lc2407)树状数组求区间最值。支持操作：
    // 1. 单点修改
    // 2. 区间目标值查询
    // 上述操作时间复杂度均为O(logn * logn)，最大支持1e5的数据规模
    // 使用时注意下标从1开始，否则更新下标0时将无限循环
    class bit {
    public:
        vector<int>tree; // 树状数组
        vector<int>nums; // 原数组
        int n;

        bit(int _n) : n(_n), tree(_n + 1), nums(_n + 1) {}

        int lowbit(int x) {
            return x & -x;
        }

        // 目标值定义, 此例为最大值
        int choose(int a, int b) {
            return max(a, b);
        }

        // 查询[a, b]之间的目标值，如果要求前缀最大值，那么用logn的写法即可
        int query(int a, int b) {
            int ret = nums[b];
            while (b >= a) {
                ret = choose(ret, nums[b]);
                b--;
                for (; b - lowbit(b) >= a; b -= lowbit(b)) {   // 如果是b - lowbit(b) + 1 >= a，在a==1时会出问题
                    ret = choose(ret, tree[b]);
                }
            }
            return ret;
        }

        // 修改下标为idx的数为val
        void update(int idx, int val) {
            nums[idx] = val;
            tree[idx] = val;
            while (idx <= n) {
                int lx = lowbit(idx);
                // 假设现在树状数组维护的是区间最大值。在单点修改时，如果把nums[8]改小了，那么如果tree[8]保存的最大值正好就是nums[8]，那么tree[8]要由tree[7], tree[6], tree[4]中的某个数取代
                for (int i = 1; i < lx; i <<= 1) {
                    tree[idx] = choose(tree[idx], tree[idx - i]);
                }
                idx += lx;
            }
        }
    };

    int lengthOfLIS(vector<int>& nums, int k) {
        int N = 1e5 + 10;
        bit tr(N);
        int cnt = 0;
        for (auto i: nums) {
            if (i == 1) {
                tr.update(1, 1);
            } else {
                int ma = tr.query(max(1, i - k), i-1);
                tr.update(i, ma + 1);
            }
        }
        return tr.query(1, N);
    }
};
复杂度

如果一定要用树状数组维护区间最值，那么其查询和更新的复杂度就不再是O(logn)了，而是O(loglogn)。

需要注意的是，在类似2736. 最大和查询 - 力扣（LeetCode）的题目中，由于只需要求前缀和，因此query函数可以直接用O(logn)的写法；由于已经存在于树中的元素不可能删去，因此下标为x的元素不会减小，update函数也可以采用O(logn)的写法。

参考

树状数组维护区间最值 - Grary - 博客园 (cnblogs.com)

__END__