Python Good Practice of Bisect
L \u2264 M \u2264 R or S[:i] \u2264 S[i:j] \u2264 S[j:] where S is the prefix sum array.\nGiven that all elements are non-negative, S is a non decreasing array 
`L \u2264 M \u2264 R` or `S[:i] \u2264 S[i:j] \u2264 S[j:]` where S is the prefix sum array.\nGiven that all elements are non-negative, S is a non decreasing array so we can use binary search to search a valid range of `M` for each index `i`.\nSuppose `M`\'s left end is `i+1` and right end range is `[j, k)`, `ans += k-j` for `nums[i]`.\n\nThe idea is easy to come up, but the implementation is a good practice of `bisect`. Which value should we search? Which end point should we use? Plus the prefix array `S[i] = sum(nums[:i])` which actually doesn\'t include `nums[i]`. That could be tricky.\n\nSince left end is fixed to be `i+1` for `nums[i]`, it could be `i` for `nums[i-1]`, we can use `S[i]` as `L` when we actually checking the contribution from `nums[i-1]`. And `M` is `S[j]-S[i]` and `R` is `S[n]-S[j]`.\n\nI\'m using `[j, k)` as right end\'s range, a.k.a an inclusive `j` end and exclusive `k` so I should search `j`  as the smallest value that makes `L \u2264 M` or `S[i] \u2264 S[j]-S[i]`. And since `k` is exclusive, I should search `k` as the smallest value that makes `M > R` or `S[j]-S[i] > S[n]-S[j]`. Note `k` is exclusive so `k-1` is the right end of the valid range which should guarantee `M \u2264 R`. \n\nSo we should use `bisect_left` for both searches. For `k`, as `S[j]-S[i] > S[n]-S[j]` or `S[j] > (S[i]+S[n])/2`, I searched  `(S[i]+S[n])//2 + 1`.\n\nAnd all the search should be in range `[i+1, n)` as `len(sub_array) > 0`, we can use the `lo` and `hi` parameter provided by `bisect`.\n\nLast, once `S[i] > S[n]/3`, we don\'t have to search any further since `min(M, R) < S[n]/3 < S[i]`.\n\n```\ndef waysToSplit(nums):\n\tn = len(nums)\n\tS = [0]\n\tfor x in nums:\n\t\tS.append(S[-1]+x)\n\tans, s = 0, S[n]\n\tfor i in range(1, n-1):\n\t\tif S[i] > s/3:\n\t\t\tbreak\n\t\tj = bisect.bisect_left(S, S[i]<<1, i+1, n)\n\t\tk = bisect.bisect_left(S, ((s+S[i])>>1)+1, j, n)\n\t\tans += k - j\n\treturn ans % (10**9+7)\n```
['Python']