[Python] Binary Search O(nlogn)
Our goal is to find two indices i,j, such that 0 <= i < j < n-1, and sum(nums[0:i+1]) <= sum(nums[i+1:j+1]) <= sum(nums[j+1:]). in fact, let s be the prefix sum
Our goal is to find two indices i,j, such that 0 <= i < j < n-1, and sum(nums[0:i+1]) <= sum(nums[i+1:j+1]) <= sum(nums[j+1:]). in fact, let s be the prefix sum array, it is same as the following inequalities:\n\ns[i] <= s[j] - s[i]\ns[j] - s[i] <= s[n-1] - s[j]\nor\ns[j] >= 2\\*s[i]\n s[j] <=(s[i] + s[n-1]) / 2\n \nWe can use another array s to keep track of prefix sum of nums. Notice that \n1. for each i, nums[i] >= 0, so s is non-decreasing. \n2. for fixed i, since s is non-decreasing, we want to find boundaries of j, on one hand, we want j to be as small as possible (left bound) but keep the mid part sum greater or equal than left sum. On the other hand, we want j to be as large as possible (right bound) but in the meantime keep the right part sum greater or equal than mid sum. \n\nFor each i, we do binary search for j twice, j_small and j_big based on above inequalities. Add j_big - j_small to our result.\n```\nclass Solution:\n    def waysToSplit(self, nums: List[int]) -> int:\n\t\t# let s be the prefix sum of nums, s[i] is the prefix sum of nums[0:i+1]\n        # iterate i from 0 to n-3, find smallest j such that si <= sj - si\n        # and biggest j such that sj - si <= sn-1 - sj\n        MOD = 10**9+7\n        n = len(nums)\n        s = [0 for _ in range(n)]\n        cur = 0\n        # prefix sum\n        for i in range(n):\n            cur += nums[i]\n            s[i] = cur\n        res = 0\n        for i in range(n-2):\n            j_small = max(bisect.bisect_left(s, 2*s[i]), i+1)\n            j_big = min(bisect.bisect_right(s, (s[i] + s[n-1])/2), n-1)\n            # print(j_small)\n            # print(j_big)\n            if j_small <= j_big:\n                res = (res + j_big - j_small) % MOD\n        return res\n```
[]