Python [binary search prefix sums]
Once again we encounter the theme where we need to binary search over prefix sums. The idea is to exploit the monotonicity of the prefix sum array which can be 
Once again we encounter the theme where we need to binary search over prefix sums. The idea is to exploit the monotonicity of the prefix sum array which can be searched in logarithmic time. Here we consider all splits ending at index `i` (where `i >= 2`) and find the leftmost index `j` and rightmost index `k` for which valid splits can be produced. That means we can have `k - j + 1` splits at `i`-th iteration. We need a left and right binary search to find `j` and `k`.\n\nThis time, however, it is slightly tricky, as we compare three sums during binary search. If `P[mi] <= P[i] - P[mi] <= x` is satisfied we have a valid condition and proceed as usual. Otherwise we need to split based on outcome. There are three more cases as shown in else-if statements below; basically, if the left sum is too large we increase `lo`, if the mid sum is too large we decrease `hi`. This will eventually terminate the while-loop; but we may not have a valid index (if the sums are not possible to satisfy, consider for example `[9 8 7]`). We therefore check the index at termination one last time and return an invalid index which will be checked in the main loop (`0` is invalid in prefix sum array).\n\nRemark: This is also an instructive question on how `bisect_left` and `bisect_right` are implemented. For the former we use `mi = lo + hi >> 1` whereas for the latter we have `mi = lo + hi + 1 >> 1`. But why do we do this? Let\'s say we have `lo = 0` and `hi = 1` and both indices satisfy the requirment. For `bisect_left` we want to get `0` and for `bisect_right` we want `1`. While `lo + hi >> 1 = 1 // 2 = 0`, `lo + hi + 1 >> 1 = 2 // 2 = 1` and forgetting this will also cause infinite loop!\n\nTime: `O(N logN)`\nSpace: `O(N)`\n\n```python\nclass Solution:\n    def bisect_left(self, P, i, x):\n        lo, hi = 1, i - 1\n        while lo < hi:\n            mi = lo + hi >> 1\n            if P[mi] <= P[i] - P[mi] <= x:\n                hi = mi\n            elif P[i] - P[mi] > x:\n                lo = mi + 1\n            elif P[mi] > x:\n                hi = mi - 1\n            elif P[mi] > P[i] - P[mi]:\n                hi = mi - 1        \n        return lo if P[lo] <= P[i] - P[lo] <= x else 0\n    \n    \n    def bisect_right(self, P, i, x):\n        lo, hi = 1, i - 1\n        while lo < hi:\n            mi = lo + hi + 1 >> 1\n            if P[mi] <= P[i] - P[mi] <= x:\n                lo = mi\n            elif P[i] - P[mi] > x:\n                lo = mi + 1\n            elif P[mi] > x:\n                hi = mi - 1\n            elif P[mi] > P[i] - P[mi]:\n                hi = mi - 1\n        return lo if P[lo] <= P[i] - P[lo] <= x else 0\n    \n    \n    def waysToSplit(self, nums):\n        ans = 0\n        P = [0] + list(accumulate(nums))\n        for i in range(2, len(nums)):\n            x = P[-1] - P[i]\n            j = self.bisect_left(P, i, x)\n            k = self.bisect_right(P, i, x)\n            if j == 0 or k == 0:\n                continue\n            ans += k - j + 1\n            ans = ans % (10**9 + 7)\n        return ans\n```
[]