记录 7 的前缀和:
根据 lowBit 函数,c[7] + c[6] + c[4],即分别代表 c[7] + c[5:6] + c[1:4]
一个简单的理解:
7 - 011|1,代表 011 为前缀,1 ~ 1 之间的和
6 - 01|10,代表 01 为前缀,01 ~ 10 之间的和
4 - 0|100,代表 0 为前缀,001 ~ 100 之间的和
Python Sorted Containers — Sorted Containers 2.4.0 documentation
from sortedcontainers import SortedList
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
s = SortedList()
for i in range(n - 1, -1, -1):
less = s.bisect_left(nums[i])
ans[i] = less
s.add(nums[i])
return ans