Divide & Conquer
Do some details write up after google interview...
https://leetcode.com/problems/reverse-pairs/discuss/97268
good article on the concept, BST (Red Black, AVL tree), BIT, Segment Tree, MergeSort embedding,...
315. Count of Smaller Numbers After Self
327. Count of Range Sum
Forleetcode 315, applying the sequential recurrence relation (withjfixed), the subproblemCreads:find the number of elements out of visited ones that are smaller than current element, which involves searching on “dynamic searching space”; applying the partition recurrence relation, we have a subproblemC:for each element in the left half, find the number of elements in the right half that are smaller than it, which can be embedded into the merging process by noting that these elements are exactly those swapped to its left during the merging process.
Forleetcode 327, applying the sequential recurrence relation (withjfixed) on the pre-sum array, the subproblemCreads:find the number of elements out of visited ones that are within the given range, which again involves searching on “dynamic searching space”; applying the partition recurrence relation, we have a subproblemC:for each element in the left half, find the number of elements in the right half that are within the given range, which can be embedded into the merging process using the two-pointer technique.
Anyway, hope these ideas can sharpen your skills for solving array-related problems.
Dynamic Search Space Concept
BST: searching is O(logn), each time after search, the element is also added to the search space... in logn time...
Indexing Skills in Divide and Conquer
Sometimes, we deliberate extending left and right as from original elements list. In this case, left and right are the boundary for easier computation for base case and etc.
Then the base case will be if(right - left <= 1) return 0; which is with just boundaries.