Comment on page

# 307.Range-Sum-Query---Mutable

## 题目描述

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.

## 代码

### Approach #1 FenwickTree (Binary indexed tree)

class NumArray {
FenwickTree tree;
int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
tree = new FenwickTree(nums.length);
for (int i = 0; i < nums.length; i++) {
tree.update(i + 1, nums[i]);
}
}
public void update(int i, int val) {
tree.update(i + 1, val - nums[i]);
nums[i] = val;
}
public int sumRange(int i, int j) {
return tree.query(j + 1) - tree.query(i);
}
}
class FenwickTree {
int sums[]; // 从 index = 1 开始
public FenwickTree(int n) {
sums = new int[n + 1];
}
public void update(int i, int delta) {
while (i < sums.length) {
sums[i] += delta;
i += i & -i;
}
}
public int query(int i) {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= i & -i;
}
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);
*/

### Approach #2 Segment Tree

update time O(logn)
class NumArray {
SegmentTree segmentTree;
public NumArray(int[] nums) {
segmentTree = new SegmentTree(nums);
}
public void update(int i, int val) {
segmentTree.update(i, val);
}
public int sumRange(int i, int j) {
return segmentTree.search(i, j);
}
}
class SegmentTree {
public SegmentTreeNode root;
public SegmentTree(int[] nums) {
root = build(nums);
}
public int search(int start, int end) {
return searchHelper(root, start, end);
}
private int searchHelper(SegmentTreeNode root, int start, int end) {
if (root == null || start > end) return 0;
if (root.start == start && root.end == end) return root.sum;
int mid = root.start + (root.end - root.start) / 2;
int leftSum = searchHelper(root.left, Math.max(root.start, start), Math.min(mid, end));
int rightSum = searchHelper(root.right, Math.max(start, mid + 1), Math.min(root.end, end));
return leftSum + rightSum;
}
public void update(int index, int val) {
updateHelper(root, index, val);
}
private void updateHelper(SegmentTreeNode root, int index, int val) {
if (root == null) return;
if (root.start == root.end && index == root.start) {
root.sum = val;
return;
}
int mid = root.start + (root.end - root.start) / 2;
if (index <= mid) {
updateHelper(root.left, index, val);
} else {
updateHelper(root.right, index, val);
}
root.sum = root.left.sum + root.right.sum;
}
private SegmentTreeNode build(int[] nums) {
return buildHelper(0, nums.length - 1, nums);
}
private SegmentTreeNode buildHelper(int start, int end, int[] nums) {
if (start == end) return new SegmentTreeNode(start, end, nums[start]);
int mid = start + (end - start) / 2;
SegmentTreeNode leftChild = buildHelper(start, mid, nums);
SegmentTreeNode rightChild = buildHelper(mid + 1, end, nums);
SegmentTreeNode root = new SegmentTreeNode(start, end, leftChild.sum + rightChild.sum);
root.left = leftChild;
root.right = rightChild;
return root;
}
}
class SegmentTreeNode {
int sum;
int start, end;
SegmentTreeNode left, right;
public SegmentTreeNode(int start, int end, int sum) {
this.sum = sum;
this.start = start;
this.end = end;
left = right = null;
}
}

### #3

// Author: Huahua, running time: 24 ms
class SegmentTreeNode {
public:
SegmentTreeNode(int start, int end, int sum,
SegmentTreeNode* left = nullptr,
SegmentTreeNode* right = nullptr):
start(start),
end(end),
sum(sum),
left(left),
right(right){}
SegmentTreeNode(const SegmentTreeNode&) = delete;
SegmentTreeNode& operator=(const SegmentTreeNode&) = delete;
~SegmentTreeNode() {
delete left;
delete right;
left = right = nullptr;
}
int start;
int end;
int sum;
SegmentTreeNode* left;
SegmentTreeNode* right;
};
class NumArray {
public:
NumArray(vector<int> nums) {
nums_.swap(nums);
if (!nums_.empty())
root_.reset(buildTree(0, nums_.size() - 1));
}
void update(int i, int val) {
updateTree(root_.get(), i, val);
}
int sumRange(int i, int j) {
return sumRange(root_.get(), i, j);
}
private:
vector<int> nums_;
std::unique_ptr<SegmentTreeNode> root_;
SegmentTreeNode* buildTree(int start, int end) {
if (start == end) {
return new SegmentTreeNode(start, end, nums_[start]);
}
int mid = start + (end - start) / 2;
auto left = buildTree(start, mid);
auto right = buildTree(mid + 1, end);
auto node = new SegmentTreeNode(start, end, left->sum + right->sum, left, right);
return node;
}
void updateTree(SegmentTreeNode* root, int i, int val) {
if (root->start == i && root->end == i) {
root->sum = val;
return;
}
int mid = root->start + (root->end - root->start) / 2;
if (i <= mid) {
updateTree(root->left, i, val);
} else {
updateTree(root->right, i, val);
}
root->sum = root->left->sum + root->right->sum;
}
int sumRange(SegmentTreeNode* root, int i, int j) {
if (i == root->start && j == root->end) {
return root->sum;
}
int mid = root->start + (root->end - root->start) / 2;
if (j <= mid) {
return sumRange(root->left, i, j);
} else if (i > mid) {
return sumRange(root->right, i, j);
} else {
return sumRange(root->left, i, mid) + sumRange(root->right, mid + 1, j);
}
}
};