树状数组

1. 问题

给定一个数组\(A\)，长度为\(n\)，数组的下标范围是\([0,n-1]\)，对数组A可进行：

1. 查询\([i,j]\)区间内的和；
2. 对位置\(i\)的值，加一个值\(x\)；

常规解决思路：抽象为“区间和查询”和“区间更新”问题，

1. 模拟，操作1的时间复杂度是\(O(n)\)，操作2的时间复杂度是\(O(1)\);
2. 前缀和，操作1的时间复杂度是\(O(1)\)，操作2的时间复杂度是\(O(n)\);

2. 定义

为了平衡操作1和操作2，引进了树状数组\(C\)，即每个位置i表示原始数组的一个区间，值\(C[i]\)表示的是原始数组\(A\)中\([i-lowbit(i)+1, i]\)区间之和，其中\(lowbit(i)\) 表示数字i的二进制表示中，位数最低的1所代表的值，如：

个人理解：最低位的1的位置表示区间的长度，如\((1000)_{2}\)表示\([1,8]\)的区间。

3. 操作

1. 二进制位
2. 区间添加
3. 区间查询

class TreeArray{
    
    vector<int> tr;
    vector<int> nums;
    int n;
    
    int lowBit(int x){
        return x & -x;
    }
    void add(int x, int u){
        for(int i=x; i<=n; i+=lowBit(i)){
            tr[i] += u;
        }    
    }
    int query(int x){
        int ans = 0;
        for(int i=x; i> 0; i -= lowBit(i)){
            ans += tr[i];
        }
        return ans;
    }
    
    // 初始化
    // for(int i=0; i< n;i++){
    //    add(i+1, nums[i]);
    //}
    
    // 区间和
    // sumRange: query(right+1) - query(left);
};

4. 复杂度

时间复杂度：\(O(\log(n))\)

空间复杂度：\(O(n)\)