307. Range Sum Query – Mutable(Medium)

该题目是一个区间求和及更新问题，使用树状数组（Binary Indexed Tree）求解。

相关文章：1057. Stack (30)

需要注意的是：

1.采用两个数组，一个是原始数据数组，一个是树状数组；

2.树状数组的下标需要从1开始，不然在使用(x&-x)时恒为0；

3.更新完树状数组后，原数组也要进行更新（卡在这里）；

 

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

AC代码：

class NumArray {
public:
	vector<int> num;
	vector<int> tree;

	NumArray(vector<int> &nums) {
	    //初始化两个数组，一个是num，用来存储原来的数组
		num = nums;
		//一个是树状数组，存储和信息
		tree = vector<int>(nums.size() + 1, 0);
		for (int i = 0; i < nums.size(); i++)
		{//采用add操作进行更新
			add(i + 1, nums[i]);
		}
	}

	void update(int i, int val) {
	    //求出差值，进行add
		int diff = val - num[i];
		add(i + 1, diff);
		//由于update操作设计到val-num[i]，所以除了更新树状数组，原数组也需要更新
		num[i] = val;
	}

	int sumRange(int i, int j) {
	    //求出1到j+1的和，求出1到i的和，然后进行相减
		return get(j+1) - get(i);
	}
	//x=0时返回0，所以x必须>=1
	int lowbit(int x)
	{
		return (x&-x);
	}
	void add(int x, int value)
	{
		for (int i = x; i < tree.size(); i += lowbit(i))
			tree[i] += value;
	}
	
	//get操作是得到1到x的和
	int get(int x)
	{
		int sum = 0;
		for (int i = x; i; i -= lowbit(i))
			sum += tree[i];
		return sum;
	}
};

// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);