Data Structures19 sections · 729 units
Open in Course

Problem - Range Sum Query 2D Mutable

2D segment tree application

Given a 2D matrix, implement:

  • update(row, col, val): Update matrix[row][col] to val
  • sumRegion(row1, col1, row2, col2): Return sum of rectangle

Example:

matrix = [[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]]
sumRegion(2,1,4,3)  8
update(3,2,2)
sumRegion(2,1,4,3)  10

This requires either 2D segment tree or 2D BIT (Binary Indexed Tree).

Constraints: matrix up to 200×200200 \times 200, up to 10410^4 operations.