Leetcode Problem 308. Range Sum Query 2D - Mutable

308. Range Sum Query 2D - Mutable

Leetcode Solutions

UsingD Binary Indexed Tree (BIT) / Fenwick Tree

  1. Initialize a 2D BIT with the same dimensions as the input matrix.
  2. Populate the BIT with the initial values of the matrix using the update method.
  3. For each update call, adjust the BIT to reflect the change in value at the specified cell.
  4. For each sumRegion call, calculate the sum of the specified rectangle by querying the BIT for the cumulative sum from the origin to the lower right corner and subtracting the cumulative sums that overlap outside the rectangle.
  5. To query the BIT, iterate from the specified index towards the origin by subtracting the least significant bit (LSB) from the index at each step.
  6. To update the BIT, iterate from the specified index towards the end of the matrix dimensions by adding the LSB to the index at each step.
UML Thumbnail

Brute Force Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...