# LeetCode 307: Range Sum Query - Mutable

## Problem Restatement

We are given an integer array `nums`.

We need to implement a class called `NumArray` that supports two operations:

| Operation | Meaning |
|---|---|
| `update(index, val)` | Change `nums[index]` to `val` |
| `sumRange(left, right)` | Return the sum from `left` through `right`, inclusive |

Unlike LeetCode 303, the array is mutable. Values can change after initialization.

The official problem expects many updates and many range queries, so recomputing sums from scratch every time is too slow. ([github.com](https://github.com/doocs/leetcode/blob/main/solution/0300-0399/0307.Range%20Sum%20Query%20-%20Mutable/README_EN.md?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Update | Change one array value |
| Query | Sum over an inclusive interval |
| Output | Integer range sum |
| Goal | Efficient updates and queries |

Class shape:

```python
class NumArray:

    def __init__(self, nums: list[int]):
        ...

    def update(self, index: int, val: int) -> None:
        ...

    def sumRange(self, left: int, right: int) -> int:
        ...
```

## Examples

Example:

```python
nums = [1, 3, 5]
obj = NumArray(nums)
```

Query:

```python
obj.sumRange(0, 2)
```

This computes:

```python
1 + 3 + 5 = 9
```

Output:

```python
9
```

Now update:

```python
obj.update(1, 2)
```

The array becomes:

```python
[1, 2, 5]
```

Now query again:

```python
obj.sumRange(0, 2)
```

Result:

```python
1 + 2 + 5 = 8
```

Output:

```python
8
```

## First Thought: Direct Updates and Direct Queries

We could store the array normally.

For `update`, simply overwrite the value.

```python
nums[index] = val
```

For `sumRange`, loop from `left` to `right`.

```python
total = 0

for i in range(left, right + 1):
    total += nums[i]
```

This works.

But one query may scan many elements.

If there are many operations, total runtime becomes large.

## Prefix Sums No Longer Work Well

In LeetCode 303, prefix sums solved the immutable version.

But now updates change the array.

Suppose:

```python
nums = [1, 3, 5]
```

Prefix sums are:

```python
[0, 1, 4, 9]
```

If we update:

```python
nums[1] = 2
```

then every later prefix value changes.

We would need to rebuild many entries.

That makes updates expensive.

We need a structure supporting:

| Operation | Desired Complexity |
|---|---|
| Update | Fast |
| Range Sum | Fast |

## Key Insight

We need a data structure that stores partial sums efficiently.

A Fenwick Tree, also called a Binary Indexed Tree (BIT), does exactly this.

It supports:

| Operation | Complexity |
|---|---:|
| Point update | `O(log n)` |
| Prefix sum | `O(log n)` |
| Range sum | `O(log n)` |

The idea is:

1. Store sums of carefully chosen ranges.
2. Use binary properties of indices to move through those ranges efficiently.

## Lowest Set Bit

Fenwick Tree navigation depends on the lowest set bit.

For any positive integer:

$$
lowbit(x)=x\ \&\ (-x)
$$

Examples:

| `x` | Binary | `lowbit(x)` |
|---|---|---:|
| `1` | `0001` | `1` |
| `2` | `0010` | `2` |
| `3` | `0011` | `1` |
| `4` | `0100` | `4` |
| `6` | `0110` | `2` |

This value tells us the size of the range represented by a tree node.

## Fenwick Tree Structure

Fenwick Tree uses 1-based indexing internally.

Suppose:

```python
nums = [1, 3, 5, 7]
```

Internally:

| Tree Index | Stored Range Sum |
|---|---|
| `1` | `[1]` |
| `2` | `[1, 2]` |
| `3` | `[3]` |
| `4` | `[1, 2, 3, 4]` |

Each node stores a partial prefix sum.

## Prefix Sum Query

To compute prefix sum up to index `i`:

1. Add `tree[i]`
2. Move left by removing the lowest set bit

```python
i -= i & -i
```

Repeat until `i == 0`.

This jumps through logarithmically many ranges.

## Point Update

When updating one element:

1. Compute the difference:
   
```python
delta = new_value - old_value
```

2. Add `delta` to all Fenwick nodes covering that position.

Move upward using:

```python
i += i & -i
```

## Range Sum Formula

A range sum can be written as:

$$
sum(left,right)=prefix(right)-prefix(left-1)
$$

So if we can compute prefix sums efficiently, range sums are also efficient.

## Algorithm

Initialization:

1. Store a copy of the original array.
2. Create a Fenwick tree array.
3. Insert each value using point updates.

Update:

1. Compute the change from old value.
2. Update the original array.
3. Propagate the difference through the Fenwick tree.

Range Query:

1. Compute prefix sum up to `right`.
2. Compute prefix sum up to `left - 1`.
3. Return the difference.

## Correctness

Each Fenwick tree node stores the sum of a specific contiguous range determined by its lowest set bit.

When performing an update at index `i`, every Fenwick node whose represented range contains `i` is updated by the same difference. Therefore, all stored partial sums remain correct after the update.

The prefix sum procedure repeatedly jumps to parent ranges using:

```python
i -= i & -i
```

These ranges are disjoint and together exactly cover all elements from index `1` through the requested position. Therefore, their sum equals the correct prefix sum.

A range sum from `left` to `right` equals:

```python
prefix(right) - prefix(left - 1)
```

because the elements before `left` cancel out.

Since both prefix sums are correct, the computed range sum is also correct.

Therefore, the algorithm always returns correct answers after any sequence of updates.

## Complexity

| Operation | Time | Space |
|---|---:|---:|
| Constructor | `O(n log n)` | `O(n)` |
| Update | `O(log n)` | `O(1)` |
| Prefix Sum | `O(log n)` | `O(1)` |
| Range Sum | `O(log n)` | `O(1)` |

The tree contains `n + 1` elements because of 1-based indexing.

## Implementation

```python
class FenwickTree:

    def __init__(self, size: int):
        self.n = size
        self.tree = [0] * (size + 1)

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

    def query(self, index: int) -> int:
        total = 0

        while index > 0:
            total += self.tree[index]
            index -= index & -index

        return total

class NumArray:

    def __init__(self, nums: list[int]):
        self.nums = nums[:]
        self.bit = FenwickTree(len(nums))

        for i, num in enumerate(nums):
            self.bit.update(i + 1, num)

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

        self.nums[index] = val

        self.bit.update(index + 1, delta)

    def sumRange(self, left: int, right: int) -> int:
        return (
            self.bit.query(right + 1)
            - self.bit.query(left)
        )
```

## Code Explanation

The Fenwick tree constructor creates:

```python
self.tree = [0] * (size + 1)
```

Index `0` is unused.

The update operation propagates changes upward.

```python
while index <= self.n:
    self.tree[index] += delta
    index += index & -index
```

Each jump moves to the next node covering a larger range.

The query operation computes a prefix sum.

```python
while index > 0:
    total += self.tree[index]
    index -= index & -index
```

Each jump removes the current lowest set bit, moving toward smaller prefix ranges.

In `NumArray`, we store a copy of the array:

```python
self.nums = nums[:]
```

We need this to compute update differences later.

During initialization:

```python
for i, num in enumerate(nums):
    self.bit.update(i + 1, num)
```

We insert every number into the Fenwick tree.

The tree uses 1-based indexing, so we use `i + 1`.

For updates:

```python
delta = val - self.nums[index]
```

Only the difference matters.

Then propagate that difference through the tree.

```python
self.bit.update(index + 1, delta)
```

Range sums use two prefix sums:

```python
return (
    self.bit.query(right + 1)
    - self.bit.query(left)
)
```

## Testing

```python
def run_tests():
    arr = NumArray([1, 3, 5])

    assert arr.sumRange(0, 2) == 9

    arr.update(1, 2)

    assert arr.sumRange(0, 2) == 8

    arr.update(0, 4)

    assert arr.sumRange(0, 1) == 6

    single = NumArray([7])

    assert single.sumRange(0, 0) == 7

    single.update(0, 10)

    assert single.sumRange(0, 0) == 10

    negatives = NumArray([-1, -2, -3, -4])

    assert negatives.sumRange(0, 3) == -10
    assert negatives.sumRange(1, 2) == -5

    negatives.update(2, 5)

    assert negatives.sumRange(0, 3) == -2

    zeros = NumArray([0, 0, 0])

    assert zeros.sumRange(0, 2) == 0

    zeros.update(1, 7)

    assert zeros.sumRange(0, 2) == 7

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Basic example | Standard update and query |
| Multiple updates | Confirms state stays consistent |
| Single element | Smallest valid array |
| Negative values | Handles subtraction correctly |
| Zero values | Neutral-element behavior |
| Full-range queries | Checks complete prefix logic |