一. 题目描写叙述
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) -> 8Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.
二. 题目分析
题目在Range Sum Query - Immutable一题的基础上添加的难度，要求在输入数组nums后，可以改动数组的元素，每次仅仅改动一个元素。相同要实现求数组的某个区间和的功能。
假设在http://blog.csdn.net/liyuefeilong/article/details/50551662 一题的做法上稍加改进。是可以实现功能的，可是会超时。
这时阅读了一些文章后才发现原来经典的做法（包含前一题）是使用树状数组来维护这个数组nums。其插入和查询都能做到O(logn)的复杂度，十分巧妙。
关于树状数组，下面博文描写叙述得非常好：
http://blog.csdn.net/int64ago/article/details/7429868
三. 演示样例代码
// 超时
class NumArray {
public:
NumArray(vector<int> &nums) {
if (nums.empty()) return;
else
{
sums.push_back(nums[0]);
//求得给定数列长度
int len = nums.size();
for (int i = 1; i < len; ++i)
sums.push_back(sums[i - 1] + nums[i]);
}
}
void update(int i, int val) {
for (int k = i; k < nums.size(); ++k)
sums[k] += (val - nums[i]);
nums[i] = val;
}
int sumRange(int i, int j) {
return sums[j] - sums[i - 1];
}
private:
vector<int> nums;
//存储数列和
vector<int> sums;
};
// 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);// 使用树状数组实现的代码AC，复杂度为O(logn)
class NumArray {
private:
vector<int> c;
vector<int> m_nums;
public:
NumArray(vector<int> &nums) {
c.resize(nums.size() + 1);
m_nums = nums;
for (int i = 0; i < nums.size(); i++){
add(i + 1, nums[i]);
}
}
int lowbit(int pos){
return pos&(-pos);
}
void add(int pos, int value){
while (pos < c.size()){
c[pos] += value;
pos += lowbit(pos);
}
}
int sum(int pos){
int res = 0;
while (pos > 0){
res += c[pos];
pos -= lowbit(pos);
}
return res;
}
void update(int i, int val) {
int ori = m_nums[i];
int delta = val - ori;
m_nums[i] = val;
add(i + 1, delta);
}
int sumRange(int i, int j) {
return sum(j + 1) - sum(i);
}
};
// 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);四. 小结
之前仅仅是听过，这是第一次使用树状数组，这是维护数组的一个非常好的思想。须要深入学习！