Using Segment Tree Range Minimum Query (C++)
This problem can also be solved using segment trees with range minimum queries as well. Here, for a given range , the segment tree should return the index of th
This problem can also be solved using segment trees with range minimum queries as well. Here, for a given range , the segment tree should return the *index* of the minimum value of that range(not the minimum value itself but the index of that value). So we can calculate the answer for that range and then check the answer on the left side of the index and on the right side of the index for that range. And we will also maintain a prefix sum array for getting the sum of elements in a given range.\nTime Complexity : O(NlogN)\n\n```\nusing ll = long long;\nclass Solution {\npublic:\n    ll mod = 1e9+7;\n    int minVal(int x, int y) { return (x < y)? x: y; } \n    int getMid(int s, int e) { return s + (e -s)/2; } \n    int RMQUtil(int *st, int ss, int se, int qs, int qe, int index, vector<int>& arr) \n    {  \n        if (qs <= ss && qe >= se) return st[index]; \n        if (se < qs || ss > qe) return INT_MAX; \n        int mid = getMid(ss, se);\n        int in1 = RMQUtil(st, ss, mid, qs, qe, 2*index+1, arr);\n        int in2 = RMQUtil(st, mid+1, se, qs, qe, 2*index+2, arr);\n        if(in1 == INT_MAX && in2 == INT_MAX) return INT_MAX;\n        else if(in1 == INT_MAX) return in2;\n        else if(in2 == INT_MAX) return in1;\n        return (arr[in1] <= arr[in2] ? in1 : in2);\n    } \n    int RMQ(int *st, int n, int qs, int qe, vector<int>& arr) { \n        if (qs < 0 || qe > n-1 || qs > qe) { \n            return -1; \n        } \n        return RMQUtil(st, 0, n-1, qs, qe, 0,arr); \n    } \n    int constructSTUtil(vector<int>& arr, int ss, int se,int *st, int si) { \n        if (ss == se) { \n            st[si] = ss; \n            return ss; \n        } \n        int mid = getMid(ss, se);\n        int in1 = constructSTUtil(arr, ss, mid, st, si*2+1);\n        int in2 = constructSTUtil(arr, mid+1, se, st, si*2+2);\n        st[si] = (arr[in1] <= arr[in2] ? in1 : in2); \n        return st[si]; \n    } \n    int *constructST(vector<int>& arr, int n) { \n        int x = (int)(ceil(log2(n)));\n        int max_size = 2*(int)pow(2, x) - 1; \n        int *st = new int[max_size]; \n        constructSTUtil(arr, 0, n-1, st, 0);  \n        return st; \n    }\n    void query(int l, int r, vector<ll>& pre, int* st, vector<int>& arr, ll& maxv){\n        if(l>r) return;\n        int in = RMQ(st, arr.size(), l, r, arr);\n        ll prod = (pre[r] - (l>0?pre[l-1]:0)) * arr[in];\n        maxv = max(maxv, prod);\n        query(l, in-1, pre, st, arr, maxv);\n        query(in+1, r, pre, st, arr, maxv);\n    }\n    int maxSumMinProduct(vector<int>& nums) {\n        int n = nums.size();\n        vector<ll> pre(n);\n        for(int i=0; i<n; i++) pre[i] = nums[i];\n        for(int i=1; i<n; i++) pre[i] += pre[i-1];\n        ll maxv = LLONG_MIN;\n        int* st = constructST(nums, n);\n        query(0,n-1,pre,st,nums,maxv);\n        maxv %= mod;\n        return maxv;\n    }\n};\n```
['Tree']