C++ | A Clean Implementation
Suppose we split our array into 3 parts, with sum as a    |    (sum - (a + b)    |    b. To satisfy the constraints, we must have\n\na <= sum - (a + b) and sum 
Suppose we split our array into 3 parts, with sum as `a    |    (sum - (a + b)    |    b`. To satisfy the constraints, we must have\n\n`a <= sum - (a + b)` and `sum - (a + b) <= b`. \n\nSuppose, we fix `b`, then we have `(sum - 2b) <= a <= (sum - b)/2`.\n\nSo, we need to fix each possible `b`, and find out the the number of elements in the range `[low, high]` which are to the left of the segment containing `b`. (Note that we have to reserve atleast one block for the mid element, so, if the suffix segment starts at `i`, we only have to look for `a` in the region `[0, i - 2]`).\n\nSo, this brings us to another abstraction, **How to find the number of elements in an inclusive range?**. Notice that the prefix sum array is always sorted (in case of non negative integers). So, we can use the `upper_bound` and `lower_bound` feature in STL. Recall that `lower_bound` returns the iterator to the first element which is not less than `key`, while `upper_bound` returns an iterator to the first element which is strictly greater than key. Hence, all elements in between lie in our inclusive range.\n\n\nTo summarise, iterate through each suffix, leave one block for middle element, and binary search the permissible elements in the prefix. \n\nTime complexity is `O(n log(n))`\n```\nconst int mod = 1e9 + 7;\n\nint count_bet(vector<int> &a, int ind, int low, int high) {\n    if(low > high) return 0;\n    \n    auto l_itr = lower_bound(a.begin(), a.begin() + ind, low);\n    auto r_itr = upper_bound(a.begin(), a.begin() + ind, high);\n    return (r_itr - l_itr);\n}\n\nclass Solution {\npublic:\n    int waysToSplit(vector<int>& a) {\n        int n = a.size();\n\t\t\n        auto pref = a;\n        for(int i = 1; i < n; i++) {\n            pref[i] += pref[i - 1];\n        }\n        \n        int sum = pref.back();\n        long long cnt = 0;\n        \n        int suf = 0;\n        for(int i = n - 1; i >= 2; i--) {\n            suf += a[i];\n            auto in_bet = count_bet(pref, i - 1, sum - 2*suf, (sum - suf)/2);\n            cnt = (cnt + in_bet) % mod;\n        }\n        \n        return cnt;\n    }\n};\n```
[]