LeetCode 307. 区域和检索 - 数组可修改（树状数组）

示例:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

说明:
数组仅可以在 update 函数下进行修改。
你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

class NumArray {
	int *sum = NULL;
	int n;
public:
    NumArray(vector<int>& nums) {
    	if(nums.empty())
    		return;
    	n = nums.size();
    	sum = new int [n];
    	sum[0] = nums[0];
        for(int i = 1; i < nums.size(); ++i)
        	sum[i] = sum[i-1]+nums[i];
    }
    
    void update(int i, int val) {
    	if(!sum)
    		return;
    	int differ;
    	if(i == 0)
    		differ = val-sum[i];
    	else
    		differ = val-(sum[i]-sum[i-1]);
        for(int k = i; k < n; ++k)
        	sum[k] += differ;
    }
    
    int sumRange(int i, int j) {
    	if(!sum)
    		return 0;
        if(i != 0)
        	return sum[j]-sum[i-1];
        return sum[j];
    }
};

class NumArray {
    vector<int> v;
    vector<int> copy;
    int N;
public:
    NumArray(vector<int>& nums) {
        N = nums.size();
        v.resize(N+1,0);//树状数组要求下标从1开始
        copy.resize(N+1,0);
        for(int i = 0; i < N; ++i)
            update(i,nums[i]);
    }
    
    void update(int i, int val) {
        int delta = val-copy[i+1];
        copy[i+1] += delta;
        i++;
        for( ;i <= N; i+= lowbit(i))
            v[i] += delta;
    }
    
    int sumRange(int i, int j) {
        return getsum(j)-getsum(i-1);
    }

    int getsum(int i)
    {
        int ans = 0;
        i++;
        for(; i > 0; i-= lowbit(i))
            ans += v[i];
        return ans;
    }

    //树状数组
    int lowbit(int m)
    {
        return m&(-m);
    }
};