Data Structures19 sections · 729 units
Open in Course

Problem - Count Smaller After Self

BIT for per-element counts

Given an integer array nums, return an array where counts[i] is the number of smaller elements to the right of nums[i]. Example: nums =[5,2,6,1]= [5, 2, 6, 1] returns [2,1,1,0][2, 1, 1, 0]. You solved this with segment trees. The BIT solution is cleaner:

1.1. Coordinate compress

2.2. Process right to left

3.3. For each element: query prefix count, then update Constraints: up to 10510^5 elements.