Python 3 | Binary Search | Explanation
Explanation\n- Calculate prefix sum and store at pre_sum\n- Iterate each index i and consider it as the ending index of the 1st segment\n- Do binary search on t
### Explanation\n- Calculate prefix sum and store at `pre_sum`\n- Iterate each index `i` and consider it as the ending index of the 1st segment\n- Do _**binary search**_ on the 2nd segment ending index. This is doable because `pre_sum` is a non-decreasing array\n\t- `[i+1, j]` is the shortest possible segment of the 2nd segment (`bisect_left`)\n\t\t- Condition to find: `pre_sum[i] * 2 <= pre_sum[j]`\n\t\t- Meaning the 2nd segment sum will not be less than the 1st segment sum\n\t- `[i+1, k-1]` is the longest possible segment of the 2nd segment (`bisect_right`)\n\t\t- Condition to find: `pre_sum[k-1] - pre_sum[i] <= pre_sum[-1] - pre_sum[k-1]`\n\t\t- Meaning the 3rd segment sum will not be less than the 2dn segment sum\n\t- For example, all combinations below will be acceptable\n\t```\n\t\t\t# [0, i], [i+1, j], [j+1, n-1]\n\t\t\t# [0, i], [i+1, j+1], [j+2, n-1]\n\t\t\t# [0, i], [i+1, ...], [..., n-1]\n\t\t\t# [0, i], [i+1, k-2], [k-1, n-1]\n\t\t\t# [0, i], [i+1, k-1], [k, n-1]\n\t```\n- Don\'t forget to handle the edge case when `k == n`\n- Time: `O(NlogN)`\n- Space: `O(N)`\n### Implementation\n```\nclass Solution:\n    def waysToSplit(self, nums: List[int]) -> int:\n        mod, pre_sum = int(1e9+7), [nums[0]]\n        for num in nums[1:]:                               # create prefix sum array\n            pre_sum.append(pre_sum[-1] + num)\n        ans, n = 0, len(nums)\n        for i in range(n):                                 # pre_sum[i] is the sum of the 1st segment\n            prev = pre_sum[i]                              # i+1 is the starting index of the 2nd segment\n            if prev * 3 > pre_sum[-1]: break               # break loop if first segment is larger than the sum of 2 & 3 segments\n                \n            j = bisect.bisect_left(pre_sum, prev * 2, i+1) # j is the first possible ending index of 2nd segment\n                \n            middle = (prev + pre_sum[-1]) // 2             # last possible ending value of 2nd segment\n            k = bisect.bisect_right(pre_sum, middle, j+1)  # k-1 is the last possible ending index of 2nd segment\n            if k-1 >= n or pre_sum[k-1] > middle: continue # make sure the value satisfy the condition since we are using bisect_right here\n            ans = (ans + min(k, n - 1) - j) % mod          # count & handle edge case\n        return ans\n```
['Binary Search', 'Python', 'Python3']