How hard is LeetCode 307. Range Sum Query - Mutable?

LeetCode 307. Range Sum Query - Mutable is rated Medium on LeetCode.

What topics does LeetCode 307. Range Sum Query - Mutable cover?

LeetCode 307. Range Sum Query - Mutable is tagged Design, Binary Indexed Tree, Segment Tree, Array and Divide and Conquer on LeetCode.

Range Sum Query - Mutable — LeetCode 307 Python Solution

MediumDesignBinary Indexed TreeSegment TreeArrayDivide and Conquer

Problem: #307
Reading time: 7 min
Source: leetcode.com

The 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.

Example

Input: ["NumArray", "sumRange", "update", "sumRange"]
Output: [null, 9, null, 8]
Explanation: NumArray numArray = new NumArray([1, 3, 5]);

Python solution

Python

class BinaryIndexedTree:
    __slots__ = ["n", "c"]

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

    def update(self, x: int, delta: int):
        while x <= self.n:
            self.c[x] += delta
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x > 0:
            s += self.c[x]
            x -= x & -x
        return s


class NumArray:
    __slots__ = ["tree"]

    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)

Complexity

Measure	Complexity
Time	O(n log n) (typical)
Space	O(log n) auxiliary

Frequently asked questions

How hard is LeetCode 307. Range Sum Query - Mutable?: LeetCode 307. Range Sum Query - Mutable is rated Medium on LeetCode.
What topics does LeetCode 307. Range Sum Query - Mutable cover?: LeetCode 307. Range Sum Query - Mutable is tagged Design, Binary Indexed Tree, Segment Tree, Array and Divide and Conquer on LeetCode.