Skip to content

Latest commit

 

History

History
57 lines (36 loc) · 1.91 KB

0304-range-sum-query-2d-immutable.adoc

File metadata and controls

57 lines (36 loc) · 1.91 KB
Raw

304. Range Sum Query 2D - Immutable

{leetcode}/problems/range-sum-query-2d-immutable/[LeetCode - Range Sum Query 2D - Immutable^]

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (_row_1, _col_1) and lower right corner (_row_2, _col_2).

{image_attr}

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given 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 // return 8 (红色矩形框的元素总和)
sumRegion(1, 1, 2, 2) -> 11 // return 11 (绿色矩形框的元素总和)
sumRegion(1, 2, 2, 4) -> 12 // return 12 (蓝色矩形框的元素总和)

Note:

  1. You may assume that the matrix does not change.

  2. There are many calls to sumRegion function.

  3. You may assume that _row_1 ≤ _row_2 and _col_1 ≤ _col_2.

思路分析

{image_attr}
{image_attr} 
link:{sourcedir}/_0304_RangeSumQuery2DImmutable.java[role=include]