> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Range Sum Query - Mutable Python Solution

> Tested Python solution for LeetCode 307 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 307, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Divide and Conquer](/catalog/topics/divide-and-conquer), [Design](/catalog/topics/design), [Binary Indexed Tree](/catalog/topics/binary-indexed-tree), [Segment Tree](/catalog/topics/segment-tree), Sqrt Decomposition. [View on LeetCode](https://leetcode.com/problems/range-sum-query-mutable/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 307   # by problem number
lcpy gen -s range_sum_query_mutable   # by problem name
```

## Problem

Given an integer array `nums`, handle multiple queries of the following types:

* **Update** the value of an element in `nums`.
* 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]`).

### Examples

```
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 * 10^4`
* `-100 <= nums[i] <= 100`
* `0 <= index < nums.length`
* `-100 <= val <= 100`
* `0 <= left <= right < nums.length`
* At most `3 * 10^4` calls will be made to `update` and `sumRange`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/range_sum_query_mutable/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/range_sum_query_mutable/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class NumArray:
    # Time: __init__ O(n), update O(log n), sum_range O(log n)
    # Space: O(n)
    def __init__(self, nums: list[int]) -> None:
        self.n = len(nums)
        self.nums = nums
        self.tree = [0] * (self.n + 1)
        for i, value in enumerate(nums, start=1):
            self.tree[i] += value
            parent = i + (i & -i)
            if parent <= self.n:
                self.tree[parent] += self.tree[i]

    def update(self, index: int, val: int) -> None:
        self._add(index + 1, val - self.nums[index])
        self.nums[index] = val

    def sum_range(self, left: int, right: int) -> int:
        return self._prefix(right + 1) - self._prefix(left)

    def _add(self, i: int, delta: int) -> None:
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def _prefix(self, i: int) -> int:
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total
```

## Complexity

| Time | Space |
| - | - |
| **init** O(n), update O(log n), sum\_range O(log n) | O(n) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.