Description:
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
Link:
https://leetcode.com/problems/range-sum-query-mutable/
解题方法：
- Brute force is very straight forward, and pretty easy to implement.
-
Segment tree:
We can use an array to store our segment tree.
Check 小fu's video on youtube
Time Complexity：
Brute force: n^2
Segment tree: nLogn
完整代码：
class NumArray {
vector<int> tree;
int size;
public:
NumArray(vector<int>& nums) {
size = nums.size();
if(!size)
return;
tree = vector<int>(size * 2);
// Build the segment tree.
for(int i = 0; i < size; i++) {
tree[size + i] = nums[i];
}
int i = size - 1;
while(i >= 1) {
tree[i] = tree[i * 2] + tree[i * 2 + 1];
i--;
}
}
void update(int i, int val) {
if(i >= size)
return;
int index = i + size;
int delt = val - tree[index];
while(index > 0) {
tree[index] += delt;
index /= 2;
}
}
int sumRange(int i, int j) {
if(i == j)
return tree[size + i];
int low, high;
if(i > j) {
low = j + size;
high = i + size;
} else {
low = i + size;
high = j + size;
}
int sum = 0;
// low <= high not low < high, this is very important!!!
while(low <= high) {
if(low % 2 != 0) {
sum += tree[low++];
}
if(high % 2 == 0) {
sum += tree[high--];
}
low /= 2;
high /= 2;
}
// While low == high, we will always calculate one of em into sum during loop.
// So we dont need to add extra tree[low or high] here.
// sum += tree[low];
return sum;
}
};
/**
* 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);
*/
网友评论