LeetCode 307: Range Sum Query - Mutable Solution in Python – A Step-by-Step Guide

What Is LeetCode 307: Range Sum Query - Mutable?

In LeetCode 307: Range Sum Query - Mutable, you’re given an integer array, and you need to build a data structure that supports two operations: updating any element and computing the sum of any range of elements. For example, with an array [1, 3, 5], you might update index 1 to 2 (making it [1, 2, 5]) and then query the sum from index 0 to 2 (getting 8). This problem builds on static range sum ideas, like LeetCode 303: Range Sum Query - Immutable, but adds the twist of mutability.

Problem Statement

• Input: An integer array nums and method calls:
• NumArray(nums): Initialize with the array.
• update(index, val): Update nums[index] to val.
• sumRange(left, right): Return sum of elements from left to right (inclusive).
• Output: Sum for each sumRange call; no explicit return for update.
• Rules: Indices are 0-based and within bounds.

Constraints

• 1 <= nums.length <= 3 * 10⁴
• -100 <= nums[i] <= 100
• 0 <= index < nums.length
• -100 <= val <= 100
• 0 <= left <= right < nums.length
• At most 3 * 10⁴ calls to update and sumRange.

Examples

• Input: ["NumArray", "sumRange", "update", "sumRange"], [[[1,3,5]], [0,2], [1,2], [0,2]]
• Output: [null, 9, null, 8]
• Init: [1, 3, 5]
• Sum(0,2): 1+3+5 = 9
• Update(1,2): [1, 2, 5]
• Sum(0,2): 1+2+5 = 8
• Input: ["NumArray", "update", "sumRange"], [[[7,-1]], [0,0], [0,1]]
• Output: [null, null, -1]

Understanding the Problem: Dynamic Range Sums

To solve LeetCode 307: Range Sum Query - Mutable in Python, we need a class that initializes with an array and handles updates and range sum queries efficiently. A naive approach—storing the array and summing on demand—takes O(n) per query, too slow for many calls. Instead, we’ll use:

• Best Solution (Segment Tree): O(n) build, O(log n) update/query, O(n) space—balanced and fast.
• Alternative Solution (Binary Indexed Tree): O(n) build, O(log n) update/query, O(n) space—compact and clever.

Let’s start with the Segment Tree, explained in a way that’s easy to follow.

Best Solution: Segment Tree

Why This Is the Best Solution

The Segment Tree is the top choice for LeetCode 307 because it’s a versatile, tree-based structure that handles both updates and range queries in O(log n) time, with O(n) space. It’s like a pyramid where each level summarizes ranges, letting you zoom in or out quickly. For dynamic range problems, it’s a powerhouse—intuitive once you see it in action and perfect for this task!

How It Works

Picture a Segment Tree as a hierarchy:

• Step 1: Build the Tree:
• Create a tree where each node represents a range sum.
• Leaf nodes hold individual array values; parent nodes sum their children.
• For [1, 3, 5], the tree might look like: root (9) → [left (4), right (5)] → [1, 3] and [5].
• Step 2: Update:
• Change a leaf node, then update all ancestors up to the root.
• Step 3: Query:
• For a range, combine node sums that cover it, skipping irrelevant branches.
• Step 4: Why It Works:
• Logarithmic height means fast updates and queries.
• Precomputed sums speed up range calculations.

It’s like a smart calculator that updates and sums in a snap!

Step-by-Step Example

Example: nums = [1, 3, 5]

• Build:
• Tree array (size 2n): [0, 9, 4, 5, 1, 3, 0, 0] (0s for padding).
• Index 1 (root) = 9, 2 (left) = 4 (1+3), 3 (right) = 5, 4 = 1, 5 = 3.
• SumRange(0, 2):
• Range 0-2: Root (1) covers 0-2, return 9.
• Update(1, 2):
• Leaf at 5 becomes 2.
• Update parent (2): 1+2 = 3.
• Update root (1): 3+5 = 8.
• Tree: [0, 8, 3, 5, 1, 2, 0, 0].
• SumRange(0, 2):
• Root now 8, return 8.

Code with Detailed Line-by-Line Explanation

Copy codeclass NumArray:
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)  # 2n size for segment tree
        # Build tree: leaves at n to 2n-1, parents upward
        for i in range(self.n, 2 * self.n):
            self.tree[i] = nums[i - self.n]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index: int, val: int) -> None:
        # Start at leaf
        pos = self.n + index
        self.tree[pos] = val
        # Update parents
        while pos > 1:
            left = pos if pos % 2 == 0 else pos - 1
            right = pos if pos % 2 == 1 else pos + 1
            self.tree[pos // 2] = self.tree[left] + self.tree[right]
            pos //= 2

    def sumRange(self, left: int, right: int) -> int:
        # Start at leaves
        l = self.n + left
        r = self.n + right
        sum = 0
        # Climb tree, adding relevant sums
        while l <= r:
            if l % 2 == 1:  # l is right child
                sum += self.tree[l]
                l += 1
            if r % 2 == 0:  # r is left child
                sum += self.tree[r]
                r -= 1
            l //= 2
            r //= 2
        return sum

• Init: O(n)
• Lines 4-6: Size tree, place leaves.
• Lines 7-9: Build parents bottom-up.
• Update: O(log n)
• Lines 12-14: Set leaf value.
• Lines 15-19: Update ancestors to root.
• SumRange: O(log n)
• Lines 22-24: Start at leaf positions.
• Lines 25-33: Climb, add nodes covering range.
• Space: O(n)—tree array.

This is like a dynamic sum machine!

Alternative Solution: Binary Indexed Tree (BIT)

Why an Alternative Approach?

The Binary Indexed Tree (BIT) offers a sleek alternative—O(log n) for updates and queries, O(n) space. It’s less intuitive but more space-efficient than a Segment Tree, using bit operations to manage cumulative sums. It’s like a minimalist scoreboard—perfect for coders who love clever tricks!

How It Works

Think of BIT as a cumulative sum tracker:

• Step 1: Build:
• Array where each index stores the sum of a range, updated via bit manipulation.
• Step 2: Update:
• Add difference to affected indices using least significant bit (LSB).
• Step 3: Query:
• Compute range sum as difference of prefix sums.
• Step 4: Why It Works:
• Logarithmic updates/queries via binary structure.

Step-by-Step Example

Example: nums = [1, 3, 5]

• Build: BIT = [0, 1, 4, 5] (1-based indexing).
• SumRange(0, 2):
• Prefix(2) = 9, Prefix(-1) = 0, Sum = 9.
• Update(1, 2):
• Diff = -1, update BIT: [0, 1, 3, 5].
• SumRange(0, 2):
• Prefix(2) = 8, Sum = 8.

Code for BIT Approach

Copy codeclass NumArray:
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.n = len(nums)
        self.bit = [0] * (self.n + 1)
        for i in range(self.n):
            self._update_bit(i + 1, nums[i])

    def _update_bit(self, index: int, val: int):
        while index <= self.n:
            self.bit[index] += val
            index += index & (-index)  # Next index via LSB

    def _get_sum(self, index: int):
        sum = 0
        while index > 0:
            sum += self.bit[index]
            index -= index & (-index)  # Parent via LSB
        return sum

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

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

• Time: O(n) build, O(log n) update/query.
• Space: O(n)—BIT array.

It’s a compact sum wizard!

Comparing the Two Solutions

• Segment Tree (Best):
• Pros: O(log n) update/query, versatile.
• Cons: More space (2n).
• BIT (Alternative):
• Pros: O(log n) update/query, compact.
• Cons: Less intuitive.

Segment Tree wins for clarity.

Additional Examples and Edge Cases

• [1], update(0,2), sum(0,0): 2.
• [1, -1], sum(0,1): 0.

Both handle these smoothly.

Complexity Breakdown

• Segment Tree: Build O(n), Update/Query O(log n), Space O(n).
• BIT: Build O(n), Update/Query O(log n), Space O(n).

Both are fast; Segment Tree is more visual.

Key Takeaways

• Segment Tree: Hierarchical sums—powerful!
• BIT: Bit magic—efficient!
• Python: Arrays and loops shine—see [Python Basics](/python/basics).
• Ranges: Dynamic queries are cool.

Final Thoughts: Master Range Sums

LeetCode 307: Range Sum Query - Mutable in Python is a dynamic data structure challenge. Segment Trees offer a clear, robust solution, while BIT provides a lean alternative. Want more? Try LeetCode 303: Range Sum Query - Immutable or LeetCode 315: Count of Smaller Numbers After Self. Ready to query? Head to Solve LeetCode 307 on LeetCode and sum it up today!