Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Range Sum Query - Mutable
Bookmark
Input
Standard
Simple
Single Update
Custom
nums
=
[1, 3, 5, 7, 9, 11]
,
operations
=
[{"type":"update","index":2,"val":10},{"type":"sumRange","left":1,"right":4}]
NumArray([1, 3, 5, 7, 9, 11])
update(2, 10)
sumRange(1, 4)
=
?
nums
0
0
0
0
0
0
0
1
2
3
4
5
bit
0
0
0
0
0
0
1
2
3
4
5
6
each bit[i] stores the sum of a power-of-two block ending at i
NumArray([1, 3, 5, 7, 9, 11])
update(2, 10)
sumRange(1, 4)
=
?
nums
0
0
0
0
0
0
0
1
2
3
4
5
bit
0
0
0
0
0
0
1
2
3
4
5
6
each bit[i] stores the sum of a power-of-two block ending at i
NumArray([1, 3, 5, 7, 9, 11])
update(2, 10)
sumRange(1, 4)
=
?
nums
1
0
0
0
0
0
0
1
2
3
4
5
bit[1]
i
bit
1
0
0
0
0
0
1
2
3
4
5
6
bit[1] +=
1
·
i += (i & -i) =
2
NumArray([1, 3, 5, 7, 9, 11])
update(2, 10)
sumRange(1, 4)
=
?
nums
1
3
0
0
0
0
0
1
2
3
4
5
bit
1
1
0
1
0
0
1
2
3
4
5
6
insert
nums[1] = 3
(delta =
3
)
NumArray([1, 3, 5, 7, 9, 11])
update(2, 10)
sumRange(1, 4)
=
?
nums
1
3
5
0
0
0
0
1
2
3
4
5
bit[3]
i
bit
1
4
5
4
0
0
1
2
3
4
5
6
bit[3] +=
5
·
i += (i & -i) =
4
NumArray([1, 3, 5, 7, 9, 11])
update(2, 10)
sumRange(1, 4)
=
?
nums
1
3
5
7
0
0
0
1
2
3
4
5
bit[4]
i
bit
1
4
5
16
0
0
1
2
3
4
5
6
bit[4] +=
7
·
i += (i & -i) =
8
NumArray([1, 3, 5, 7, 9, 11])
update(2, 10)
sumRange(1, 4)
=
?
nums
1
3
5
7
9
0
0
1
2
3
4
5
bit[6]
i
bit
1
4
5
16
9
9
1
2
3
4
5
6
bit[6] +=
9
·
i += (i & -i) =
8
NumArray([1, 3, 5, 7, 9, 11])
update(2, 10)
sumRange(1, 4)
=
?
nums
1
3
5
7
9
11
0
1
2
3
4
5
bit
1
4
5
16
9
20
1
2
3
4
5
6
tree built · O(log n) per update & query
NumArray([1, 3, 5, 7, 9, 11])
update(2, 10)
sumRange(1, 4)
=
?
nums
1
3
10
7
9
11
0
1
2
3
4
5
bit[4]
i
bit
1
4
10
21
9
20
1
2
3
4
5
6
bit[4] +=
5
·
i += (i & -i) =
8
NumArray([1, 3, 5, 7, 9, 11])
update(2, 10)
sumRange(1, 4)
=
?
nums
1
3
10
7
9
11
0
1
2
3
4
5
bit[4]
i
bit
1
4
10
21
9
20
1
2
3
4
5
6
prefix(4)
: sum += bit[4] =
30
· i -= (i & -i) =
0
NumArray([1, 3, 5, 7, 9, 11])
update(2, 10)
sumRange(1, 4)
=
29
nums
1
3
10
7
9
11
0
1
2
3
4
5
bit
1
4
10
21
9
20
1
2
3
4
5
6
all operations processed
algo
master
.
io
Step:
Fenwick tree: each cell stores a partial sum.
0 / 29
Input
Standard
Simple
Single Update
Custom
nums
=
[1, 3, 5, 7, 9, 11]
,
operations
=
[{"type":"update","index":2,"val":10},{"type":"sumRange","left":1,"right":4}]
0 / 29
algo
master
.
io
Step:
Fenwick tree: each cell stores a partial sum.
