> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/307-range-sum-query-mutable.md).

# 307 Range Sum Query - Mutable

## 307. [Range Sum Query - Mutable](https://leetcode.com/problems/range-sum-query-mutable/description/)

## 1. Question

Given an integer arraynums, find the sum of the elements between indicesiandj(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:**

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

## 2. Implementation

**(1) Binary Index Tree**

```java
class NumArray {
    BIT bit;
    int[] nums;
    int size;

    public NumArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return ;
        }
        size = nums.length;
        this.nums = nums;
        bit = new BIT(size);

        for (int i = 0; i < size; i++) {
            bit.update(i + 1, nums[i]);
        }
    }

    public void update(int i, int val) {
        bit.update(i + 1, val - nums[i]);
        nums[i] = val;
    }

    public int sumRange(int i, int j) {
        return bit.query(j + 1) - bit.query(i);
    }
}

class BIT {
    int[] sums;

    public BIT(int n) {
        sums = new int[n + 1];
    }

    public void update (int index, int val) {
        while (index < sums.length) {
            sums[index] += val;
            index += index & -index;
        }
    }

    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += sums[index];
            index -= index & -index;
        }
        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);
 */
```

## 3. Time & Space Complexity

**Binary Indexed Tree**: 时间复杂度: Binary Indexed Tree构造O(NlogN), update(logN), sumRange(logN), 空间复杂度O(N)