# Range Sum Query - Mutable
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/range-sum-query-mutable)
Canonical: https://scaleengineer.com/dsa/problems/range-sum-query-mutable
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Binary Indexed Tree, Segment Tree
**Companies:** [Google](https://scaleengineer.com/companies/google)
---
## Problem
Given an integer array `nums`, handle multiple queries of the following types:

1. **Update** the value of an element in `nums`.
2. Calculate the **sum** of the elements of `nums` between indices `left` and `right` **inclusive** where `left <= right`.

Implement the `NumArray` class:

* `NumArray(int[] nums)` Initializes the object with the integer array `nums`.
* `void update(int index, int val)` **Updates** the value of `nums[index]` to be `val`.
* `int sumRange(int left, int right)` Returns the **sum** of the elements of `nums` between indices `left` and `right` **inclusive** (i.e. `nums[left] + nums[left + 1] + ... + nums[right]`).

**Example 1:**

**Input**
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
**Output**
[null, 9, null, 8]

**Explanation**
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

**Constraints:**

* `1 <= nums.length <= 3 * 104`
* `-100 <= nums[i] <= 100`
* `0 <= index < nums.length`
* `-100 <= val <= 100`
* `0 <= left <= right < nums.length`
* At most `3 * 104` calls will be made to `update` and `sumRange`.

# Approaches
## Brute Force
The most straightforward approach is to simulate the operations directly on the array. We store a copy of the input array `nums`. When an update is requested, we modify the element at the specific index. When a sum range is requested, we iterate through the given range and calculate the sum on the fly.
**Time:** *   **Constructor**: O(N) to create a copy of the input array.
*   **`update`**: O(1) as it's a direct array access.
*   **`sumRange`**: O(N) in the worst case, as we might need to iterate through the entire array. · **Space:** O(N), where N is the number of elements in the input array. This space is used to store the copy of the array.
**Pros:** Very simple to understand and implement.; The `update` operation is extremely fast, taking O(1) time.; Requires minimal extra space, just enough to store the array itself.
**Cons:** The `sumRange` operation is very slow, with a time complexity of O(N) in the worst case.; This approach will likely result in a 'Time Limit Exceeded' error for large inputs and a high number of `sumRange` queries, as specified in the problem constraints.
### Explanation
In this approach, the `NumArray` class holds a copy of the integer array. The `update` operation is efficient as it only involves a single array modification, which is a constant time operation. However, the `sumRange` operation requires iterating through all the elements from the `left` index to the `right` index. In the worst-case scenario, where the range covers the entire array, this iteration takes time proportional to the size of the array, `N`.

```java
class NumArray {
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
    }
    
    public void update(int index, int val) {
        nums[index] = val;
    }
    
    public int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += nums[i];
        }
        return sum;
    }
}
```
### Algorithm
1.  **Constructor `NumArray(int[] nums)`**: 
    *   Initialize a member variable, an integer array, with the values from the input `nums`.
2.  **Update `update(int index, int val)`**:
    *   Directly access the element at the given `index` in the stored array and set its value to `val`.
3.  **Sum Range `sumRange(int left, int right)`**:
    *   Initialize a variable `sum` to 0.
    *   Loop from `left` to `right` (inclusive).
    *   In each iteration, add the value of the element `nums[i]` to `sum`.
    *   Return the final `sum`.

## Square Root Decomposition
This approach offers a balance between the update and query operations. The idea is to divide the original array into several blocks of a fixed size, typically the square root of the array's length. We pre-calculate and store the sum of each block. An update operation only needs to modify one element in the original array and the sum of one block. A range query can then be answered by summing up full blocks and iterating over the partial elements at the boundaries of the range.
**Time:** *   **Constructor**: O(N) to build the blocks.
*   **`update`**: O(1).
*   **`sumRange`**: O(sqrt(N)). · **Space:** O(N + sqrt(N)), which simplifies to O(N). We need O(N) for the `nums` array and O(sqrt(N)) for the `blocks` array.
**Pros:** Significantly faster for range queries compared to the brute-force method.; Maintains a fast O(1) update time.; Provides a good performance balance when there's a mix of update and sum queries.
**Cons:** More complex to implement than the brute-force approach.; Not as asymptotically efficient as tree-based solutions like Segment Trees or Fenwick Trees.
### Explanation
We partition the array of size `N` into `sqrt(N)` blocks, each of size `sqrt(N)`. An auxiliary array, `blocks`, is used to store the sum of each block. 

*   **Initialization**: We iterate through the input array once to populate both our copy of the array and the `blocks` sum array. This takes O(N) time.
*   **Update**: When `nums[i]` is updated, we only need to update `nums[i]` itself and the sum of the single block it belongs to. This is an O(1) operation.
*   **Sum Range**: A query for `sumRange(left, right)` is handled by summing up elements in at most two partial blocks at the ends of the range and summing up the pre-calculated sums for all the full blocks in between. Since there are at most `sqrt(N)` blocks and each block has size `sqrt(N)`, the query time complexity is O(sqrt(N)).

```java
class NumArray {
    private int[] nums;
    private int[] blocks;
    private int len; // block size

    public NumArray(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        this.len = (int) Math.ceil(Math.sqrt(n));
        this.blocks = new int[len];
        for (int i = 0; i < n; i++) {
            blocks[i / len] += nums[i];
        }
    }
    
    public void update(int index, int val) {
        int blockIndex = index / len;
        blocks[blockIndex] = blocks[blockIndex] - nums[index] + val;
        nums[index] = val;
    }
    
    public int sumRange(int left, int right) {
        int sum = 0;
        int startBlock = left / len;
        int endBlock = right / len;

        if (startBlock == endBlock) {
            for (int i = left; i <= right; i++) {
                sum += nums[i];
            }
        } else {
            // First block (partial)
            for (int i = left; i <= (startBlock + 1) * len - 1; i++) {
                sum += nums[i];
            }
            // Middle blocks (full)
            for (int i = startBlock + 1; i < endBlock; i++) {
                sum += blocks[i];
            }
            // Last block (partial)
            for (int i = endBlock * len; i <= right; i++) {
                sum += nums[i];
            }
        }
        return sum;
    }
}
```
### Algorithm
1.  **Constructor `NumArray(int[] nums)`**:
    *   Determine the size of the array, `N`.
    *   Calculate the block size, `len = sqrt(N)`.
    *   Calculate the number of blocks needed, `numBlocks = ceil(N / len)`.
    *   Initialize a `blocks` array of size `numBlocks` with zeros.
    *   Iterate through the input `nums` from `i = 0` to `N-1`, and for each element `nums[i]`, add its value to the corresponding block: `blocks[i / len] += nums[i]`.
2.  **Update `update(int index, int val)`**:
    *   Find the block index corresponding to the update index: `blockIndex = index / len`.
    *   Update the sum in the `blocks` array by subtracting the old value and adding the new value: `blocks[blockIndex] = blocks[blockIndex] - nums[index] + val`.
    *   Update the value in the original `nums` array: `nums[index] = val`.
3.  **Sum Range `sumRange(int left, int right)`**:
    *   Determine the start and end block indices: `startBlock = left / len`, `endBlock = right / len`.
    *   Initialize `sum = 0`.
    *   **If `startBlock == endBlock`**: The range is within a single block. Iterate from `left` to `right` in the `nums` array and add to `sum`.
    *   **If `startBlock != endBlock`**:
        *   Sum the elements from `left` to the end of the `startBlock` by iterating through `nums`.
        *   Sum the values of all full blocks between `startBlock` and `endBlock` by iterating through the `blocks` array.
        *   Sum the elements from the beginning of the `endBlock` to `right` by iterating through `nums`.

## Segment Tree
A Segment Tree is a versatile binary tree data structure designed for efficient processing of range queries. For this problem, each node in the tree will store the sum of a specific range of the input array. The root represents the sum of the entire array, and each leaf represents a single element. This structure allows both `update` and `sumRange` operations to be performed in logarithmic time.
**Time:** *   **Constructor**: O(N) to build the tree.
*   **`update`**: O(log N).
*   **`sumRange`**: O(log N). · **Space:** O(N) to store the segment tree. The array representing the tree needs a size of approximately 4N to be safe.
**Pros:** Highly efficient, with logarithmic time complexity for both updates and queries.; A very general and powerful technique applicable to many range-based problems (e.g., range minimum/maximum, range XOR).
**Cons:** More complex to implement and debug compared to previous approaches.; Requires more space (typically 4N) than a Binary Indexed Tree.
### Explanation
The key idea is to pre-process the array into a tree structure where each node's value is derived from its children. An update to a single element (a leaf) only requires updating the nodes along the path from that leaf to the root. A range query can be answered by combining the values of a small number of nodes that collectively cover the query range. Since the tree is balanced and has a height of O(log N), both operations are very efficient.

```java
class NumArray {
    private int[] tree;
    private int n;

    public NumArray(int[] nums) {
        n = nums.length;
        tree = new int[4 * n];
        build(nums, 0, 0, n - 1);
    }

    private void build(int[] nums, int node, int start, int end) {
        if (start == end) {
            tree[node] = nums[start];
            return;
        }
        int mid = start + (end - start) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        build(nums, leftChild, start, mid);
        build(nums, rightChild, mid + 1, end);
        tree[node] = tree[leftChild] + tree[rightChild];
    }

    public void update(int index, int val) {
        update(0, 0, n - 1, index, val);
    }

    private void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = start + (end - start) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        if (idx <= mid) {
            update(leftChild, start, mid, idx, val);
        } else {
            update(rightChild, mid + 1, end, idx, val);
        }
        tree[node] = tree[leftChild] + tree[rightChild];
    }

    public int sumRange(int left, int right) {
        return query(0, 0, n - 1, left, right);
    }

    private int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0; // No overlap
        }
        if (l <= start && end <= r) {
            return tree[node]; // Total overlap
        }
        int mid = start + (end - start) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        int p1 = query(leftChild, start, mid, l, r);
        int p2 = query(rightChild, mid + 1, end, l, r);
        return p1 + p2;
    }
}
```
### Algorithm
1.  **Data Structure**: Use an array `tree` of size `4*N` to store the segment tree nodes.
2.  **Build `build(node, start, end)`**: This is a recursive function to build the tree.
    *   **Base Case**: If `start == end`, it's a leaf node. Set `tree[node] = nums[start]`.
    *   **Recursive Step**: Calculate `mid = start + (end - start) / 2`. Recursively call `build` for the left child `(2*node, start, mid)` and the right child `(2*node + 1, mid + 1, end)`. Then, set `tree[node] = tree[2*node] + tree[2*node + 1]`.
3.  **Update `update(node, start, end, idx, val)`**: A recursive function to update a value.
    *   **Base Case**: If `start == end`, update the leaf: `tree[node] = val`.
    *   **Recursive Step**: Determine if `idx` is in the left or right subtree. Recurse accordingly. After the recursive call returns, update the current node's sum: `tree[node] = tree[left_child] + tree[right_child]`.
4.  **Query `query(node, start, end, l, r)`**: A recursive function to find the sum of range `[l, r]`.
    *   **No Overlap**: If the node's range `[start, end]` is completely outside `[l, r]`, return 0.
    *   **Total Overlap**: If the node's range is completely inside `[l, r]`, return `tree[node]`.
    *   **Partial Overlap**: Recurse on both left and right children and return the sum of their results.

## Binary Indexed Tree (Fenwick Tree)
The Binary Indexed Tree (BIT), or Fenwick Tree, is another highly efficient data structure for this problem. It excels at calculating prefix sums and handling point updates in logarithmic time. A `sumRange(left, right)` query can be elegantly computed as `prefixSum(right) - prefixSum(left - 1)`. The BIT is often preferred over a Segment Tree for this specific problem due to its simpler implementation and lower memory overhead.
**Time:** *   **Constructor**: O(N log N) for the naive build by repeated updates.
*   **`update`**: O(log N).
*   **`sumRange`**: O(log N), as it performs two O(log N) query operations. · **Space:** O(N) to store the BIT array and a copy of the original numbers.
**Pros:** Optimal time complexity for both updates and queries.; Generally easier and shorter to implement than a Segment Tree.; More space-efficient, requiring only an array of size N+1.
**Cons:** Can be less intuitive to understand the underlying mechanism compared to a Segment Tree.; While great for prefix sum-based queries, it's less flexible than a Segment Tree for other types of range queries like range minimum/maximum.
### Explanation
A BIT uses an array where each index `i` stores the sum of a specific range of the original array. The range that `bit[i]` is responsible for is determined by the least significant bit of `i`. This clever indexing scheme allows both updates and prefix sum queries to be resolved by traversing a path of length O(log N) through the implicit tree structure.

*   **Update**: When a value `nums[i]` changes, we only need to update the `bit` entries that include `nums[i]` in their range sum. This involves following a chain of indices by repeatedly adding the lowest set bit.
*   **Query**: To find the prefix sum up to `i`, we sum up `bit` entries by following a chain of indices by repeatedly subtracting the lowest set bit.

```java
class NumArray {
    private int[] bit;
    private int[] nums;
    private int n;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        this.bit = new int[n + 1];
        for (int i = 0; i < n; i++) {
            init(i, nums[i]);
        }
    }

    // Used for initial construction
    private void init(int index, int val) {
        int i = index + 1;
        while (i <= n) {
            bit[i] += val;
            i += i & (-i); // Add last set bit
        }
    }

    public void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        int i = index + 1;
        while (i <= n) {
            bit[i] += delta;
            i += i & (-i);
        }
    }

    private int query(int index) {
        int sum = 0;
        int i = index + 1;
        while (i > 0) {
            sum += bit[i];
            i -= i & (-i); // Subtract last set bit
        }
        return sum;
    }

    public int sumRange(int left, int right) {
        return query(right) - query(left - 1);
    }
}
```
### Algorithm
1.  **Data Structure**: Use an array `bit` of size `N+1` for the tree and an array `nums` of size `N` to store the original values.
2.  **Constructor `NumArray(int[] nums)`**:
    *   Store the input `nums`.
    *   Initialize the `bit` array of size `N+1`.
    *   Iterate from `i = 0` to `N-1` and call a private update function `_update(i, nums[i])` to populate the BIT. This builds the tree.
3.  **Private Update `_update(int index, int delta)`**:
    *   Start at `i = index + 1` (to convert to 1-based indexing for BIT).
    *   Loop while `i <= N`:
        *   Add `delta` to `bit[i]`.
        *   Move to the next responsible index: `i += i & (-i)` (add the lowest set bit).
4.  **Public Update `update(int index, int val)`**:
    *   Calculate the difference: `delta = val - this.nums[index]`.
    *   Update the stored `nums` array: `this.nums[index] = val`.
    *   Call the private update `_update(index, delta)` to propagate the change through the BIT.
5.  **Query `_query(int index)`**: This calculates the prefix sum up to `index` (inclusive) in the original array.
    *   Start with `sum = 0` and `i = index + 1` (1-based).
    *   Loop while `i > 0`:
        *   Add `bit[i]` to `sum`.
        *   Move to the parent index: `i -= i & (-i)` (subtract the lowest set bit).
    *   Return `sum`.
6.  **Sum Range `sumRange(int left, int right)`**:
    *   Calculate the sum as the difference between two prefix sums: `_query(right) - _query(left - 1)`.

# Solutions
### CSharp

```csharp
class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; } public void Update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += x & - x ; } } public int Query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= x & - x ; } return s ; } } public class NumArray { private BinaryIndexedTree tree ; public NumArray ( int [] nums ) { int n = nums . Length ; tree = new BinaryIndexedTree ( n ); for ( int i = 0 ; i < n ; ++ i ) { tree . Update ( i + 1 , nums [ i ]); } } public void Update ( int index , int val ) { int prev = SumRange ( index , index ); tree . Update ( index + 1 , val - prev ); } public int SumRange ( int left , int right ) { return tree . Query ( right + 1 ) - tree . Query ( left ); } } /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * obj.Update(index,val); * int param_2 = obj.SumRange(left,right); */
```

### Java

```java
class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; } public void update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += x & - x ; } } public int query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= x & - x ; } return s ; } } class NumArray { private BinaryIndexedTree tree ; public NumArray ( int [] nums ) { int n = nums . length ; tree = new BinaryIndexedTree ( n ); for ( int i = 0 ; i < n ; ++ i ) { tree . update ( i + 1 , nums [ i ]); } } public void update ( int index , int val ) { int prev = sumRange ( index , index ); tree . update ( index + 1 , val - prev ); } public int sumRange ( int left , int right ) { return tree . query ( right + 1 ) - tree . query ( left ); } } /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * obj.update(index,val); * int param_2 = obj.sumRange(left,right); */
```

### CPP

```cpp
class BinaryIndexedTree { public: int n ; vector < int > c ; BinaryIndexedTree ( int _n ) : n ( _n ) , c ( _n + 1 ) {} void update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += x & - x ; } } int query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= x & - x ; } return s ; } }; class NumArray { public: BinaryIndexedTree * tree ; NumArray ( vector < int >& nums ) { int n = nums . size (); tree = new BinaryIndexedTree ( n ); for ( int i = 0 ; i < n ; ++ i ) tree -> update ( i + 1 , nums [ i ]); } void update ( int index , int val ) { int prev = sumRange ( index , index ); tree -> update ( index + 1 , val - prev ); } int sumRange ( int left , int right ) { return tree -> query ( right + 1 ) - tree -> query ( left ); } }; /** * Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * obj->update(index,val); * int param_2 = obj->sumRange(left,right); */
```

### Python

```python
class BinaryIndexedTree : def __init__ ( self , n ): self . n = n self . c = [ 0 ] * ( n + 1 ) @ staticmethod def lowbit ( x ): return x & - x def update ( self , x , delta ): while x <= self . n : self . c [ x ] += delta x += BinaryIndexedTree . lowbit ( x ) def query ( self , x ): s = 0 while x > 0 : s += self . c [ x ] x -= BinaryIndexedTree . lowbit ( x ) return s class NumArray : def __init__ ( self , nums : List [ int ]): self . tree = BinaryIndexedTree ( len ( nums )) for i , v in enumerate ( nums , 1 ): self . tree . update ( i , v ) def update ( self , index : int , val : int ) -> None : prev = self . sumRange ( index , index ) self . tree . update ( index + 1 , val - prev ) def sumRange ( self , left : int , right : int ) -> int : return self . tree . query ( right + 1 ) - self . tree . query ( left ) # Your NumArray object will be instantiated and called as such: # obj = NumArray(nums) # obj.update(index,val) # param_2 = obj.sumRange(left,right) ############ # Segment tree node class STNode ( object ): def __init__ ( self , start , end ): self . start = start self . end = end self . total = 0 self . left = None self . right = None class SegmentedTree ( object ): def __init__ ( self , nums , start , end ): self . root = self . buildTree ( nums , start , end ) def buildTree ( self , nums , start , end ): if start > end : return None if start == end : node = STNode ( start , end ) node . total = nums [ start ] return node mid = start + ( end - start ) / 2 root = STNode ( start , end ) root . left = self . buildTree ( nums , start , mid ) root . right = self . buildTree ( nums , mid + 1 , end ) root . total = root . left . total + root . right . total return root def updateVal ( self , i , val ): def updateVal ( root , i , val ): if root . start == root . end : root . total = val return val mid = root . start + ( root . end - root . start ) / 2 if i <= mid : updateVal ( root . left , i , val ) else : updateVal ( root . right , i , val ) root . total = root . left . total + root . right . total return root . total return updateVal ( self . root , i , val ) def sumRange ( self , i , j ): def rangeSum ( root , start , end ): if root . start == start and root . end == end : return root . total mid = root . start + ( root . end - root . start ) / 2 if j <= mid : return rangeSum ( root . left , start , end ) elif i >= mid + 1 : return rangeSum ( root . right , start , end ) else : return rangeSum ( root . left , start , mid ) + rangeSum ( root . right , mid + 1 , end ) return rangeSum ( self . root , i , j ) class NumArray ( object ): def __init__ ( self , nums ): """ initialize your data structure here. :type nums: List[int] """ self . stTree = SegmentedTree ( nums , 0 , len ( nums ) - 1 ) def update ( self , i , val ): """ :type i: int :type val: int :rtype: int """ return self . stTree . updateVal ( i , val ) def sumRange ( self , i , j ): """ sum of elements nums[i..j], inclusive. :type i: int :type j: int :rtype: int """ return self . stTree . sumRange ( i , j ) # Your NumArray object will be instantiated and called as such: # numArray = NumArray(nums) # numArray.sumRange(0, 1) # numArray.update(1, 10) # numArray.sumRange(1, 2)
```