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

## 307. Range Sum Query Mutable

## 题目地址

<https://leetcode.com/problems/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)

```java
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)

```java
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

```java
// 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);
    }
  }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/bit/307.range-sum-query-mutable.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.