How hard is LeetCode 308. Range Sum Query 2D - Mutable?

LeetCode 308. Range Sum Query 2D - Mutable is rated Medium on LeetCode.

What topics does LeetCode 308. Range Sum Query 2D - Mutable cover?

LeetCode 308. Range Sum Query 2D - Mutable is tagged Design, Binary Indexed Tree, Segment Tree, Array and Matrix on LeetCode.

Is LeetCode 308. Range Sum Query 2D - Mutable a premium problem?

Yes. LeetCode 308. Range Sum Query 2D - Mutable is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Range Sum Query 2D - Mutable — LeetCode 308 Python Solution

MediumLeetCode PremiumDesignBinary Indexed TreeSegment TreeArrayMatrix

Problem: #308
Pattern: Matrix and Grid
Reading time: 9 min
Source: leetcode.com

The problem

Given a 2D matrix matrix, handle multiple queries of the following types: Update the value of a cell in matrix. Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example

Input: ["NumMatrix", "sumRegion", "update", "sumRegion"]
Output: [null, 8, null, 10]
Explanation: NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);

Python solution

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 NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self.trees = []
        n = len(matrix[0])
        for row in matrix:
            tree = BinaryIndexedTree(n)
            for j, v in enumerate(row):
                tree.update(j + 1, v)
            self.trees.append(tree)

    def update(self, row: int, col: int, val: int) -> None:
        tree = self.trees[row]
        prev = tree.query(col + 1) - tree.query(col)
        tree.update(col + 1, val - prev)

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return sum(
            tree.query(col2 + 1) - tree.query(col1)
            for tree in self.trees[row1 : row2 + 1]
        )


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# obj.update(row,col,val)
# param_2 = obj.sumRegion(row1,col1,row2,col2)

Complexity

Measure	Complexity
Time	O(m·n)
Space	O(1) to O(m·n) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 308. Range Sum Query 2D - Mutable is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Matrix.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 308. Range Sum Query 2D - Mutable?: LeetCode 308. Range Sum Query 2D - Mutable is rated Medium on LeetCode.
What topics does LeetCode 308. Range Sum Query 2D - Mutable cover?: LeetCode 308. Range Sum Query 2D - Mutable is tagged Design, Binary Indexed Tree, Segment Tree, Array and Matrix on LeetCode.
Is LeetCode 308. Range Sum Query 2D - Mutable a premium problem?: Yes. LeetCode 308. Range Sum Query 2D - Mutable is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.