树状数组的原理

树状数组

树状数组是一种可以高效进行前缀和查询和更新的数据结构。它可以在O(logn)的时间复杂度内完成前缀和查询和更新操作，非常适合处理频繁的查询和更新操作。

树状数组的基本思想是将数组划分为若干个区间，每个区间对应一个节点，节点之间的父子关系形成一棵树。通过树状数组，可以在O(logn)的时间复杂度内完成前缀和查询和更新操作。

树状数组的主要操作包括：初始化、查询前缀和、更新元素。

树状数组的初始化

树状数组的初始化操作是将数组中的每个元素初始化为0。初始化操作的时间复杂度为O(n)。

树状数组的查询前缀和

树状数组的查询前缀和操作是通过树状数组中的节点来实现的。具体来说，查询前缀和的操作是从树状数组的根节点开始，沿着树状数组中的路径向下遍历，直到到达查询的位置。在遍历的过程中，将路径上的所有节点的值累加起来，得到查询位置的前缀和。

查询前缀和操作的时间复杂度为O(logn)。

树状数组的更新元素

树状数组的更新元素操作是通过树状数组中的节点来实现的。具体来说，更新元素的操作用于更新指定位置的元素值，并将路径上的所有节点的值进行相应的调整。

更新元素操作的时间复杂度为O(logn)。

原理

x & -x 得到 x 的二进制表示中最低位的1及其后面的0构成的数。
x & (x - 1) 得到 x 的二进制表示中最低位的1前面的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
27
class Tree{
private:
    // 树状数组
    vector<int> tr;
    // 数组长度
    int n;
public:
    // 构造函数，初始化树状数组长度
    Tree(int _n) {
        n = _n;
        tr.resize(n + 1);
    }

    // 更新树状数组
    void update(int x, int v) {
        // 从x开始，每次加上x的最低位1，直到x大于n
        for (; x <= n; x += x & -x) tr[x] += v;
    }

    // 查询树状数组
    int query(int x) {
        int res = 0;
        // 从x开始，每次减去x的最低位1，直到x为0
        for (; x; x -= x & -x) res += tr[x];
        return res;
    }
}