## Summary

In this post, I will introduce some problems using the merge sort technique.

These problems often ask, for an element at index , how many are there which satisfies a formula.

## OJ

Trick | Difficulty | |
---|---|---|

LC 1395 | Enumerate the middle element + Count #elements larger or smaller | 6 points |

LC 327 | Prefix sum + Keep diff in range | 6-7 points |

LC 493 | Count #elements larger or smaller | 6 points |

LC 315 | Count #elements larger or smaller | 6 points |

## Details

#### The Master Theorem

If is of complexity , then is of complexity

So in these problems, a key point is to keep the merge part of complexity by leveraging the sorted property.

#### Keep Difference in Range

I want to talk about the merge part of LC 327 in this section. Given two sorted array and , the problem is to count how many are there, such that

Usually, we will enumerate the left part (or the right part) by . We use two cursors and to store the boundary in the right part to satisfy the above formula.

```
int mid = left + (right - left) / 2;
int result = merge_sort(left, mid, nums) + merge_sort(mid + 1, right, nums);
int start = mid + 1, end = mid + 1;
for (int i = left; i < mid + 1; ++i) {
while (start < right + 1 && (long)nums[start] - nums[i] < lower) {
start++;
}
while (end < right + 1 && (long)nums[end] - nums[i] <= upper) {
end++;
}
result += (end - start);
}
inplace_merge(nums.begin() + left, nums.begin() + mid + 1, nums.begin() + right + 1);
return result;
```