Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← 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
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
offset =
0
result[i] = # of values after i that are smaller · BIT index = value + offset
nums
5
2
6
1
result
-
-
-
0
0
1
2
3
i
BIT
0
0
0
0
0
0
1
2
3
4
5
6
result[3] =
0
offset =
0
result[i] = # of values after i that are smaller · BIT index = value + offset
nums
5
2
6
1
result
-
-
-
0
0
1
2
3
i
idx
BIT
1
1
0
0
0
0
1
2
3
4
5
6
bit[
2
] += 1 →
1
· idx += idx & −idx →
4
offset =
0
result[i] = # of values after i that are smaller · BIT index = value + offset
nums
5
2
6
1
result
-
-
-
0
0
1
2
3
i
idx
BIT
1
1
0
1
0
0
1
2
3
4
5
6
sum += bit[
5
] =
0
· idx −= idx & −idx →
4
offset =
0
result[i] = # of values after i that are smaller · BIT index = value + offset
nums
5
2
6
1
result
-
-
1
0
0
1
2
3
i
BIT
1
1
0
1
0
0
1
2
3
4
5
6
insert x = 6
at BIT index
6
offset =
0
result[i] = # of values after i that are smaller · BIT index = value + offset
nums
5
2
6
1
result
-
-
1
0
0
1
2
3
i
BIT
1
1
0
1
0
1
1
2
3
4
5
6
query
: how many seen values <
2
? prefix [1..1]
offset =
0
result[i] = # of values after i that are smaller · BIT index = value + offset
nums
5
2
6
1
result
-
1
1
0
0
1
2
3
i
BIT
1
1
0
1
0
1
1
2
3
4
5
6
insert x = 2
at BIT index
2
offset =
0
result[i] = # of values after i that are smaller · BIT index = value + offset
nums
5
2
6
1
result
-
1
1
0
0
1
2
3
i
BIT
1
2
0
2
0
1
1
2
3
4
5
6
query
: how many seen values <
5
? prefix [1..4]
offset =
0
result[i] = # of values after i that are smaller · BIT index = value + offset
nums
5
2
6
1
result
2
1
1
0
0
1
2
3
i
BIT
1
2
0
2
0
1
1
2
3
4
5
6
result[0] =
2
offset =
0
result[i] = # of values after i that are smaller · BIT index = value + offset
nums
5
2
6
1
result
2
1
1
0
0
1
2
3
BIT
1
2
0
2
1
2
1
2
3
4
5
6
result =
[2, 1, 1, 0]
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
algo
master
.
io
Step:
Initialize BIT of size 6. Offset = 0 (so min value 1 maps to index 1). Traverse nums right to left.
