树状数组

概述

树状数组是用数组来模拟树型结构的一种数据结构，它的优势在于它可以以 O(log n) 的时间复杂度对一个数组进行单点修改和区间求和。普通的数组单点修改的时间复杂度是 O(1) ，区间求和的时间复杂度是 O(n) ，差分数组单点修改的时间复杂度是 O(n)，区间求和的复杂度是 O(1) 。树状数组则将单点修改和区间求和的复杂度都限制在了可以接受的范围内，平均意义上效率更高。

---

原理

对于原数组 A[i] ，维护一个辅助数组（也就是树状数组） C[i] ，使 C[i] = A[i-2^k+1] + A[i-2^k+2] + ... + A[i] ，其中 k 是 i 的二进制中最低位到最高位连续零的长度。

例如：

C[1] = A[1];
C[2] = A[1] + A[2];
C[3] = A[3];
C[4] = A[1] + A[2] + A[3] + A[4];
C[5] = A[5];
C[6] = A[5] + A[6];
C[7] = A[7];
C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];

通过这种方法我们可以把数组中若干个单点的和集中起来访问和维护，以达到更高的效率。

---

代码实现

lowbit：找到一个数的二进制表示中最低位的1

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

单点修改

void add(int index,int val){
    //为下标为index的元素增加val的值
    for(int i=index;i<=n;i+=lowbit(i)){
        c[index] += val;
    }
    a[index] += val;
}

区间求和

int getsum(int index){
    //求A[1]到A[index]的和
    int res=0;
    for(int i=index;i>0;i-=lowbit(i)){
        res += c[i];
    }
    return res;
}

---

例题

LeetCode 307. 区间和检索 - 数组可修改

题目描述：

给你一个数组 nums ，请你完成两类查询。

    1. 其中一类查询要求 更新 数组 nums 下标对应的值

    2. 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间 （包含） 的 nums 元素的和，其中 left <= right

实现 NumArray 类：

• NumArray(int[] nums)用整数数组 nums 初始化对象

• void update(int index, int val) 将 nums[index] 的值 更新 为 val

• int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间 （包含）的 nums 元素的 和 (即, nums[left] + nums[left + 1] + ... + nums[right])

示例1：

输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2); // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

题解：

class NumArray {
private:
    vector<int> tree;
    vector<int> nums;
    int lowbit(int x){
        return x & -x;
    }
    int query(int x){
        int ans=0;
        for(int i=x;i>0;i-=lowbit(i)) ans+=tree[i];
        return ans;
    }
    void add(int x, int num){
        for(int i=x;i<tree.size();i+=lowbit(i)) tree[i]+=num;
        return;
    }
public:
    NumArray(vector<int>& nums) {
        this->nums=nums;
        int n=nums.size();
        this->tree.resize(n+1);
        for(int i=0;i<nums.size();i++) add(i+1,nums[i]);
    }

    void update(int index, int val) {
        add(index+1,val-nums[index]);
        nums[index]=val;
    }

    int sumRange(int left, int right) {
        return query(right+1)-query(left);
    }
};