Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Range Sum Query 2D - Immutable
Bookmark
Brute Force
1D Prefix (Row-wise)
2D Prefix Sum
Input
5x5 Matrix
3x3 Matrix
All Ones
Custom
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]]
,
row1
=
2
,
col1
=
1
,
row2
=
4
,
col2
=
3
sumRegion(2, 1, 4, 3)
0
1
2
3
4
0
1
2
3
4
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)
0
1
2
3
4
0
1
2
3
4
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)
0
1
2
3
4
0
1
2
3
4
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) =
?
sumRegion(2, 1, 4, 3)
0
1
2
3
4
0
1
2
3
4
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
sum += matrix[2][1] =
2
sum =
2
sumRegion(2, 1, 4, 3)
0
1
2
3
4
0
1
2
3
4
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
sum += matrix[2][3] =
1
sum =
3
sumRegion(2, 1, 4, 3)
0
1
2
3
4
0
1
2
3
4
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
sum += matrix[3][1] =
1
sum =
4
sumRegion(2, 1, 4, 3)
0
1
2
3
4
0
1
2
3
4
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
sum += matrix[3][2] =
0
sum =
4
sumRegion(2, 1, 4, 3)
0
1
2
3
4
0
1
2
3
4
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
sum += matrix[3][3] =
1
sum =
5
sumRegion(2, 1, 4, 3)
0
1
2
3
4
0
1
2
3
4
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
sum += matrix[4][2] =
3
sum =
8
sumRegion(2, 1, 4, 3)
0
1
2
3
4
0
1
2
3
4
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
sum += matrix[4][3] =
0
sum =
8
sumRegion(2, 1, 4, 3)
0
1
2
3
4
0
1
2
3
4
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
algo
master
.
io
Step:
Start: add up every cell inside the query rectangle
0 / 11
Input
5x5 Matrix
3x3 Matrix
All Ones
Custom
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]]
,
row1
=
2
,
col1
=
1
,
row2
=
4
,
col2
=
3
0 / 11
algo
master
.
io
Step:
Start: add up every cell inside the query rectangle
