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:
The array is only modifiable by the update function.You may assume the number of calls to update and sumRange function is distributed evenly. 基本思路： 使用Binary Indexed Tree。具体可参考：https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ 尤其是下面这幅图（摘自上面的链接）： 图中，柱状高度，表示取值范围。 例如，8的高度，为【1，8】，表示BITree第8个数，存储的是【1，8】这8个数的和。 6则表示BITree中第6个数存储的是【5，6】这2个数的和。 ... 1.如果要获取【1，9】的和，该怎么办呢？ 方法就是取BiTree[8] + BiTree[9] 2.【1，3】则是BITree[2] + BiTree[3] 3. 获取【4，9】的和呢？ 则 【1，9】 - 【1，3】即可 class NumArray { vector<int> mBiTree; vector<int> mNums; int getSum(int i) { int index = i + 1; int sum = 0; while (index > 0) { sum += mBiTree[index]; index -= index & (-index); } return sum; } void init(int i, int diff) { int index = i + 1; while (index < mBiTree.size()) { mBiTree[index] += diff; index += index & (-index); } } public: NumArray(vector<int> &nums) { mNums = nums; mBiTree = vector<int>(nums.size()+1); for (int i=0; i<nums.size(); i++) { init(i, nums[i]); } } void update(int i, int val) { init(i, val - mNums[i]); mNums[i] = val; } int sumRange(int i, int j) { return getSum(j) - getSum(i-1); } }; // 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);
