#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/segment-trees/problem-range-sum-query-2d-mutable

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/segment-trees/problem-range-sum-query-2d-mutable

Repovive

Problem - Range Sum Query 2D Mutable - Segment Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

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 \times 200$ , up to $10^4$ operations.