树状数组实现原理 cpp

树状数组是一种用于快速维护数组前缀和的数据结构，其时间复杂度为 $O(logn)$。树状数组的实现基于二进制的思想，借助树状数组可以高效地进行单点更新和区间查询等操作。以下是树状数组的实现原理：

1. 数组的每个元素代表原数组中某个位置的前缀和，如下所示：
$$C_i = A_1 + A_2 + \cdots + A_i$$
其中 $C_i$ 表示原数组 $A$ 的前 $i$ 项之和。

2. 将 $C$ 数组转换成树状数组 $T$，树状数组的每个节点表示其父节点到该节点的元素和。如下所示：
$$T_i = C_{i-lowbit(i)+1} + C_{i-lowbit(i)+2} + \cdots + C_i$$
其中 $lowbit(i)$ 表示 $i$ 的二进制表示中最低位的 $1$ 所代表的值。

3. 树状数组的单点更新操作只需要将 $i$ 位置的值加上 $k$，然后依次更新其祖先节点即可：

void update(int i, int k, int n, vector<int>& tree) {
    while (i <= n) {
        tree[i] += k;
        i += lowbit(i);
    }
}

其中 $n$ 表示原数组 $A$ 的大小，$tree$ 表示树状数组。

4. 树状数组的区间查询操作只需要通过两次前缀和的差值计算出区间和即可：

int query(int i, vector<int>& tree) {
    int sum = 0;
    while (i > 0) {
        sum += tree[i];
        i -= lowbit(i);
    }
    return sum;
}

int query(int i, int j, vector<int>& tree) {
    return query(j, tree) - query(i - 1, tree);
}

其中第一个查询函数用于计算 $A_1 + A_2 + \cdots + A_i$，第二个查询函数用于计算 $A_{i+1} + A_{i+2} + \cdots + A_j$，然后两者相减即可得到区间 $[i,j]$ 的和。