c++ prefixsum
TC: O(n logn logn)\n```\nclass Solution {\npublic:\n    int waysToSplit(vector& nums) {\n        long const mod = 1e9 + 7;\n        int n = nums.size();\n      
TC: O(n logn logn)\n```\nclass Solution {\npublic:\n    int waysToSplit(vector<int>& nums) {\n        long const mod = 1e9 + 7;\n        int n = nums.size();\n        vector<long long> prefix(nums.size());\n        prefix[0] = nums[0];\n        for(int i = 1;i<nums.size();i++)\n        {\n            prefix[i] = prefix[i-1] + nums[i];\n        }\n        \n        long long count = 0;\n        for(int i = 0;i<prefix.size();i++)\n        {\n            int left = lower_bound(prefix.begin(), prefix.end(), 2*prefix[i]) - prefix.begin();\n            if(left<=i) left = i+1;\n            int start = left;\n            if(left==prefix.size()) break;\n            int right = prefix.size()-1;\n            int ans = left;\n            while(left<=right)\n            {\n                int mid = (left+(right-left)/2);\n                int right_val = prefix[n-1]-prefix[mid];\n                int left_val = prefix[mid]-prefix[i];\n                if(mid==n-1) break;\n                if(right_val >= left_val)\n                {\n                    ans = mid;\n                    left = mid+1;\n                }\n                else right = mid-1;\n            }\n            if(ans==left) continue;\n            ans = ans-start + 1;\n            count+=ans;\n        }\n        return count%mod;\n    }\n};
['C', 'Binary Tree', 'Prefix Sum']