100% Faster || Easy To Understand || C++ Code
*Using Prefix Sum and Binary Search\n *Let i and j be the left _boundary && j be the right_boundary : arr[i] <= arr[j] - arr[i] <= arr[n-1] - arr[j]\n *After Si
* ****Using Prefix Sum and Binary Search****\n* ****Let i and j be the left _boundary && j be the right_boundary : arr[i] <= arr[j] - arr[i] <= arr[n-1] - arr[j]****\n* ****After Simplifying the above inequality , we get arr[j] >= 2 * arr[i]  && arr[j] <= (arr[n-1] + arr[i])/2****\n\n1. ***Time Complexity : O(NlogN)***\n2. ***Space Complexity : O(N)***\n\n```\n    int mod = 1e9 + 7;\n    \n    int find_left_boundary(vector<int> &arr, int start, int end, int i, int n)\n    {\n        int left_boundary = n;\n        \n        while(start <= end)\n        {\n            int mid = (start + end) / 2;\n            \n            if(arr[mid] >= 2 * arr[i])\n            {\n                left_boundary = mid;\n                \n                end = mid - 1;\n            }\n            \n            else{\n                \n                start = mid + 1;\n            }\n        }\n        \n        return left_boundary;\n    }\n    \n    int find_right_boundary(vector<int> &arr, int start, int end, int i, int n)\n    {\n        int right_boundary = i;\n        \n        while(start <= end)\n        {\n            int mid = (start + end) / 2;\n            \n            if(arr[mid] <= (arr[n-1] + arr[i]) / 2)\n            {\n                right_boundary = mid;\n                \n                start = mid + 1;\n            }\n            \n            else{\n                \n                end = mid - 1;\n            }\n        }\n        \n        return right_boundary;\n    }\n    \n    int waysToSplit(vector<int>& arr) {\n        \n        int n = arr.size();\n        \n        int ans = 0;\n        \n        for(int i = 1; i < n; i++)\n        {\n            arr[i] += arr[i-1];\n        }\n        \n        for(int i = 0; i <= n - 3; i++)\n        {\n            int left_boundary = find_left_boundary(arr, i + 1, n - 2, i, n);\n            \n            int right_boundary = find_right_boundary(arr, i + 1, n - 2, i, n);\n            \n            if(right_boundary >= left_boundary)\n            {\n                ans = (ans % mod + (right_boundary - left_boundary + 1) % mod ) % mod;\n            }\n        }\n        \n        return ans;\n    }\n```
['Binary Search', 'Prefix Sum']