Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Range Sum Query 2D - Mutable
Bookmark
Brute Force
Row Prefix
2D Fenwick
Input
Standard
Simple
Update Only
matrix
=
[[3,0,1], [5,6,3], [1,2,0]]
,
operations
=
update(1, 1, 10), sumRegion(1, 1, 2, 2)
build 3×3
update(1,1)→10
sum(1,1→2,2)
=
?
matrix
2D BIT (1-indexed)
0
1
2
0
1
2
0
1
2
3
0
1
2
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
tree[i][j] sums a 2ᵃ × 2ᵇ block of the matrix ending at (i, j) · 1-indexed
build 3×3
update(1,1)→10
sum(1,1→2,2)
=
?
matrix
2D BIT (1-indexed)
0
1
2
0
1
2
0
1
2
3
0
1
2
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
tree[i][j] sums a 2ᵃ × 2ᵇ block of the matrix ending at (i, j) · 1-indexed
build 3×3
update(1,1)→10
sum(1,1→2,2)
=
?
matrix
2D BIT (1-indexed)
0
1
2
0
1
2
0
1
2
3
0
1
2
3
3
0
0
0
0
0
0
0
0
covered by tree[2][1]
0
0
0
0
0
3
3
0
0
3
0
0
0
0
0
0
tree[2][1] += 3 →
3
build 3×3
update(1,1)→10
sum(1,1→2,2)
=
?
matrix
2D BIT (1-indexed)
0
1
2
0
1
2
0
1
2
3
0
1
2
3
3
0
1
0
0
0
0
0
0
covered by tree[2][3]
0
0
0
0
0
3
3
1
0
3
3
1
0
0
0
0
tree[2][3] += 1 →
1
build 3×3
update(1,1)→10
sum(1,1→2,2)
=
?
matrix
2D BIT (1-indexed)
0
1
2
0
1
2
0
1
2
3
0
1
2
3
3
0
1
5
6
0
0
0
0
0
0
0
0
0
3
3
1
0
8
8
1
0
0
0
0
insert matrix[1][1] = 6
build 3×3
update(1,1)→10
sum(1,1→2,2)
=
?
matrix
2D BIT (1-indexed)
0
1
2
0
1
2
0
1
2
3
0
1
2
3
3
0
1
5
6
3
1
0
0
0
0
0
0
0
3
3
1
0
8
14
4
0
0
0
0
insert matrix[2][0] = 1
build 3×3
update(1,1)→10
sum(1,1→2,2)
=
?
matrix
2D BIT (1-indexed)
0
1
2
0
1
2
0
1
2
3
0
1
2
3
3
0
1
5
6
3
1
2
0
covered by tree[3][2]
0
0
0
0
0
3
3
1
0
8
14
4
0
1
3
0
tree[3][2] += 2 →
3
build 3×3
update(1,1)→10
sum(1,1→2,2)
=
?
matrix
2D BIT (1-indexed)
0
1
2
0
1
2
0
1
2
3
0
1
2
3
+
3
0
1
5
10
3
1
2
0
0
0
0
0
0
3
3
1
0
8
18
4
0
1
3
0
term 1: prefix(2, 2)
(add)
build 3×3
update(1,1)→10
sum(1,1→2,2)
=
?
matrix
2D BIT (1-indexed)
0
1
2
0
1
2
0
1
2
3
0
1
2
3
−
3
0
1
5
10
3
1
2
0
0
0
0
0
0
3
3
1
0
8
18
4
0
1
3
0
term 2: prefix(0, 2)
(subtract)
build 3×3
update(1,1)→10
sum(1,1→2,2)
=
?
matrix
2D BIT (1-indexed)
0
1
2
0
1
2
0
1
2
3
0
1
2
3
−
3
0
1
5
10
3
1
2
0
covered by tree[2][1]
0
0
0
0
0
3
3
1
0
8
18
4
0
1
3
0
sum += tree[2][1] =
9
build 3×3
update(1,1)→10
sum(1,1→2,2)
=
15
matrix
2D BIT (1-indexed)
0
1
2
0
1
2
0
1
2
3
0
1
2
3
3
0
1
5
10
3
1
2
0
0
0
0
0
0
3
3
1
0
8
18
4
0
1
3
0
results:
[15]
algo
master
.
io
Step:
Initialize 2D Binary Indexed Tree for range sum queries
0 / 53
Input
Standard
Simple
Update Only
matrix
=
[[3,0,1], [5,6,3], [1,2,0]]
,
operations
=
update(1, 1, 10), sumRegion(1, 1, 2, 2)
0 / 53
algo
master
.
io
Step:
Initialize 2D Binary Indexed Tree for range sum queries
