Learn
Practice
Newsletter
Resources
Animations
New
F
Toggle theme
0
F
0
Toggle menu
← Back to All Animations
Count of Smaller Numbers After Self
Bookmark
Input
Standard
Sorted Desc
With Duplicates
Already Sorted
Custom
nums
=
[5, 2, 6, 1]
offset =
0
result[i] = # of values after i that are smaller · BIT index = value + offset
nums
5
2
6
1
result
-
-
-
-
0
1
2
3
BIT
0
0
0
0
0
0
1
2
3
4
5
6
scan right → left · BIT (indexed by value) counts seen values smaller than each element
algo
master
.
io
Step:
Initialize BIT of size 6. Offset = 0 (so min value 1 maps to index 1). Traverse nums right to left.
0 / 33
Input
Standard
Sorted Desc
With Duplicates
Already Sorted
Custom
nums
=
[5, 2, 6, 1]
0 / 33
offset =
0
result[i] = # of values after i that are smaller · BIT index = value + offset
nums
5
2
6
1
result
-
-
-
-
0
1
2
3
BIT
0
0
0
0
0
0
1
2
3
4
5
6
scan right → left · BIT (indexed by value) counts seen values smaller than each element
algo
master
.
io
Step:
Initialize BIT of size 6. Offset = 0 (so min value 1 maps to index 1). Traverse nums right to left.
