C++ | BINARY SEARCH | NlogN
PLEASE UPVOTE IF U LIKE MY SOLUTION\n\n\nclass Solution {\n    const int M=1e9+7;\npublic:\n    int waysToSplit(vector<int>& nums) {\n        int n=nums.size();
**PLEASE UPVOTE IF U LIKE MY SOLUTION**\n\n```\nclass Solution {\n    const int M=1e9+7;\npublic:\n    int waysToSplit(vector<int>& nums) {\n        int n=nums.size();\n        \n        //calculate the prefix-sum array\n        for(int i=1;i<n;i++)\n            nums[i]+=nums[i-1];\n        \n        int count=0;\n        for(int i=0;i<=n-1;i++)\n        {\n            //we need to have at least one element in the 1st and 3rd group so we consider lo=i+1 && hi=n-2\n            int lo=i+1,hi=n-2,right=-1,left=-1;\n    \n            //we calculate the right-most valid index\n            while(lo<=hi)\n            {\n                int mid=lo+(hi-lo)/2;\n                if(nums[mid]-nums[i]<=nums.back()-nums[mid])\n                {\n                    right=mid;\n                    lo=mid+1;\n                }\n                else\n                    hi=mid-1;\n            }\n            \n            lo=i+1;hi=n-2;\n            //we calculate the left-most valid index\n             while(lo<=hi)\n            {\n                int mid=lo+(hi-lo)/2;\n                if(nums[i]<=nums[mid]-nums[i])\n                {\n                    left=mid;\n                    hi=mid-1;\n                }\n                else\n                    lo=mid+1;\n            }\n            //invalid condition check i.e. if one of the bound does not exist \n            //or left bound is greater than right bound\n            if(left==-1||right==-1||left>right)continue;\n            \n            count=(count+(right-left+1)%M)%M;\n        }\n        return count%M;\n    }\n};\n```
['Binary Tree']