Divide and conquer · HTML
Split index range [lo,hi). Recursively count relations internal to each side; with L and R sorted, use monotone pointers to count cross pairs satisfying P(L[i],R[j]), then merge.
Recognition signals
- The target counts index pairs satisfying an order or range relation.
- An i<j condition is naturally enforced by left and right index halves.
- Once both value halves are sorted, the valid partner boundary moves monotonically.
- Brute force is O(n²), while cross-half pairs can be accumulated in linear time.
- The sorted result must survive for the parent level.
False friends
| Signal | Why it is different |
|---|
| Frequency without index order | Plain sorting or hash counting may express the task more directly. |
| A non-monotone partner boundary | If j moves backward as i advances, the linear combine argument disappears. |
| Online updates | Merge counting is offline; dynamic queries favor a Fenwick or segment tree. |
Core invariant
At combine entry, both halves are sorted and internally counted. The relation pointer only advances; at exit every cross pair is counted exactly once and the parent range is sorted.
State, transition, and processing order
| Item | Definition |
|---|
| State | The value or record array, a shared buffer, accumulated count, and relation/merge pointers. |
| Transition | Solve both halves, batch-count on the sorted halves, and merge them back into the parent range. |
| Frontier / order | Postorder recursion; at each level the frontier is two sorted unconsumed suffixes plus a monotone relation boundary. |
Python skeleton
def count_inversions(nums):
a, buf = list(nums), [0] * len(nums)
def solve(lo, hi):
if hi - lo <= 1: return 0
mid = (lo + hi) // 2
count = solve(lo, mid) + solve(mid, hi)
i, j, w = lo, mid, lo
while i < mid and j < hi:
if a[i] <= a[j]:
buf[w] = a[i]; i += 1
else:
buf[w] = a[j]; j += 1; count += mid - i
w += 1
while i < mid: buf[w] = a[i]; i += 1; w += 1
while j < hi: buf[w] = a[j]; j += 1; w += 1
a[lo:hi] = buf[lo:hi]
return count
return solve(0, len(a))
Correctness sketch
- Recursion completely counts pairs internal to either half.
- When a[i]>a[j], sortedness makes every a[i:mid] greater than a[j], adding mid-i at once; otherwise advancing i cannot miss an inversion.
- Every index pair becomes cross-half exactly at its lowest common split, so it is counted once.
Complexity
| Time | Space | Parameters |
|---|
| O(n log n) | O(n) buffer plus O(log n) stack | n is element count; combine must remain O(n) per level. |
Edge cases
- whether equal values count
- empty or singleton input
- count overflow
- strict versus non-strict relation
- preserving original indices
- overwriting before counting
Error patterns
| Pattern | Why it fails / fix |
|---|
| Putting equality on the wrong branch | The <= choice determines whether duplicates enter a strict relation. |
| Counting without merging | The parent relies on sorted children; skipping restoration invalidates its pointers. |
| Resetting j for every i | That falls back to O(n²); the optimization requires a monotone boundary. |
| Confusing value pairs with index pairs | Repeated values usually represent several distinct indexed instances. |
Selection and exclusion rules
- Fix strictness and the counted identity first.
- Prove partner-boundary monotonicity after sorting.
- Restore the exact sorted summary required by the parent.
- Use a Fenwick or segment tree for online operations.
Original micro-example
| Part | Detail |
|---|
| Result | There are two pairs: (4,1) and (4,3). |
| Setup | For [4,1,3], count earlier values greater than later values. |
| Trace | The right half [1,3] is sorted; during merge, both 1 and 3 see one remaining larger left item. |
Recall prompts
My notes