[C++] Prefix Sum + Binary Search | Inline Explaination
\nclass Solution {\npublic:\n    \n    /* \n        Let i and j be two pointers which splits the array into 3 parts. \n    \n        Condition for splitting: nu
```\nclass Solution {\npublic:\n    \n    /* \n        Let i and j be two pointers which splits the array into 3 parts. \n    \n        Condition for splitting: nums[i] <= nums[j]-nums[i] <= nums.back() - nums[j];\n        \n        which can be simplified to -\n        1. nums[j] >= 2*nums[i]                     --> (condition for left boundary of j)  \n        2. nums[j] <= (nums.back() + nums[i]) / 2   --> (condition for right boundary of j)\n    */\n    \n    \n    /* function to calculate left boundary for j */\n\n    int getLeftBoundary (vector<int> & nums, int start, int end, int i, int n){\n        int bound = n;\n        \n        while(start<=end){\n            int mid = start + (end-start)/2;\n            \n            if(nums[mid] < 2*nums[i])\n                start = mid+1;\n            \n            else{\n                bound = mid;\n                end = mid-1;\n            }\n        }\n        \n        return bound;\n    }\n    \n    \n    /* Function to calculate right boundary for j */\n    \n    int getRightBoundary (vector<int> & nums, int start, int end, int i, int n){\n        int bound = i;\n\n        while(start<=end){\n            int mid = start + (end-start)/2;\n\n            if(nums[mid] > (nums[n-1] + nums[i])/2)\n                end = mid-1;\n            \n            else{\n                bound = mid;\n                start = mid+1;\n            }\n        }\n        \n        return bound;\n    }\n    \n    \n    int waysToSplit(vector<int>& nums) {\n        int n = nums.size();\n        int M = 1000000007; \n        \n        /* Computing prefix sum */\n        \n        for(int i=1; i<n; i++)\n            nums[i] += nums[i-1]; \n        \n        int ans = 0;\n        \n        /* for every i, compute leftBoundary and rightBoundary of j such that it satisfies the conditions */\n        \n        for(int i=0; i<n-2; i++){\n            \n            int leftBoundary = getLeftBoundary(nums, i+1, n-2, i, n);\n            int rightBoundary = getRightBoundary(nums, i+1, n-2, i, n);\n            \n            if(rightBoundary>=leftBoundary)\n                ans = (ans%M + (rightBoundary - leftBoundary + 1)%M)%M;\n        }\n        \n        return ans;\n    }\n};\n```
['Binary Search', 'C', 'Prefix Sum']