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.
class NumArray { public: vector<int> c; vector<int> num; NumArray(vector<int> nums) { num = nums; int n = nums.size(); c.resize(n+1); for(int i=0; i<n; i++) add(i+1, nums[i]); } int lowbit(int p) { return p & -p; } void add(int i, int num) { while(i < c.size()) { c[i] += num; i += lowbit(i); } } int sum(int i) { int r = 0; while(i > 0) { r += c[i]; i -= lowbit(i); } return r; } void update(int i, int val) { int delta = val - num[i]; num[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 obj = new NumArray(nums); * obj.update(i,val); * int param_2 = obj.sumRange(i,j); */参考 http://blog.csdn.net/u010270082/article/details/36506033
