Data Structures19 sections · 729 units
Open in Course

Problem - Count Smaller After Self

Inversion count variant

Given array AA, for each element, count how many elements to its right are smaller. Example: A=[5,2,6,1]A = [5, 2, 6, 1] returns [2,1,1,0][2, 1, 1, 0].

  • Right of 5: 2 and 1 are smaller (count 2)
  • Right of 2: 1 is smaller (count 1)
  • Right of 6: 1 is smaller (count 1)
  • Right of 1: nothing (count 0)

This you can solve with wavelet trees by querying "count less than A[i]A[i] in range [i+1,n−1][i+1, n-1]." Constraints: up to 10510^5 elements.