Data Structures19 sections · 729 units
Open in Course

Problem - Count Smaller After Self

Segment tree for inversions

Given an integer array nums, return an array counts 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].

  • Right of 5: 2 and 1 are smaller → 2
  • Right of 2: 1 is smaller → 1
  • Right of 6: 1 is smaller → 1
  • Right of 1: nothing → 0

This is "count inversions" per element, solvable with segment tree or BIT. Constraints: up to 10510^5 elements, values up to 10410^4.