T O(nlogn) S O(n) explained Soln
Since we need to divide the arr into 3 parts so that \n * sum of left <= sum of middle <= sum of right\n * \n * first optimization to save a lot of time is calc
* Since we need to divide the arr into 3 parts so that \n * sum of left <= sum of middle <= sum of right\n * \n * first optimization to save a lot of time is calculating the prefix sum in O(n) time\n * which gives us sum of values b/w any 2 index in just O(1) time.\n * \n * now our problem can be re-written as below\n * find i & j index such that\n * prefixSum[i] <= prefixSum[j]-prefixSum[i] <= prefixSum[n-1]-prefixSum[j]\n * \n * so bascially we need to iterate i thru [1..n-2] we need atleast 1 values for mid & rt sub-array\n * & for each index i, we need to find l & r such that\n *      min index l such that sum of mid-array is greater or equal to left-sub-array)\n *      max index r such that sum of mid-array is smaller than or equal to sum of rt-sub-array)\n * \n * since prefix sum is sorted we can use binary search to find our \'l\' & \'r\' index\n * at the end we return count % mod.\n```\npublic class Solution {\n    // Time O(nlogn) || Space O(n), n = length of \'nums\'\n    public int WaysToSplit(int[] nums) {\n        int n = nums.Length, count = 0, l, r;\n        long leftSum, remainingSum;\n\n        long[] prefixSum = new long[n + 1];\n        prefixSum[0] = nums[0];\n        for (int i = 1; i < n; i++)\n            prefixSum[i] = prefixSum[i-1] + nums[i];\n\n        for (int i = 0; i < n - 1; i++)\n        {\n            leftSum = prefixSum[i];\n            remainingSum = prefixSum[n-1] - leftSum;\n            if (prefixSum[n-1] < leftSum * 3) break;    // to divide array into 3 equal parts total sum should be >= thrice the sum of left-sub-array\n\n            l = SearchLeft(i + 1, leftSum);             // min index l such that sum of mid-array is greater or equal to left-sub-array)\n            r = SearchRight(i + 1, remainingSum / 2);   // max index r such that sum of mid-array is smaller than or equal to sum of rt-sub-array)\n\n            count += 1 + r - l;\n            count %= 1000000007;\n        }\n        return (int)count;\n\n\n        // local func\n        int SearchLeft(int idx, long target)\n        {\n            int mid, left = idx, rt = n - 2;\n            while (left < rt)\n            {\n                mid = left + ((rt - left) / 2);\n                if (prefixSum[mid] - leftSum >= target)\n                    rt = mid;\n                else\n                    left = mid + 1;\n            }\n            return left;\n        }\n        int SearchRight(int idx, long target)\n        {\n            int mid, left = idx, rt = n - 2;\n            while (left < rt)\n            {\n                mid = left + (1 + rt - left) / 2;\n                if (prefixSum[mid] - leftSum <= target)\n                    left = mid;\n                else\n                    rt = mid - 1;\n            }\n            return rt;\n        }\n    }\n}\n```\n![image](https://assets.leetcode.com/users/images/46e2c26e-9673-40e3-baff-e31ae1b73c73_1618600262.2265222.png)\n
['Binary Tree']