Segment Tree || Divide and Conquer || Dynamic Programming || Implementation
Approach\n# Optimal Solution for Maximum Subarray Problem Using Segment Tree\n\nWhen dealing with constraints that make a brute force approach infeasible, an op
# Approach\n# Optimal Solution for Maximum Subarray Problem Using Segment Tree\n\nWhen dealing with constraints that make a brute force approach infeasible, an optimal solution is often achievable using a data structure known as a segment tree. Let\'s consider a scenario where we have a subarray with starting and ending indices \'st\' and \'en\', and we need to determine the maximum value within this subarray. \n\nTo find the maximum, we consider four different cases:\n\n1. Taking both the first and last index into our answer.\n2. Taking the first index but not the last index into our answer.\n3. Not taking the first index but taking the last index into our answer.\n4. Not taking either the first or last index into our answer.\n\nLet\'s denote `seg[ind][i][j]` as the maximum in the range of \'st\' and \'en\', where \'i\' and \'j\' can be either 0 or 1. Here, \'i\' represents whether the first index is taken into consideration (1 means it has been taken, 0 means it has not), and similarly, \'j\' represents the last index.\n\n`seg[ind][1][1]` represents a case where both the first and last indices are taken into consideration. To find this value, we use a divide and conquer method, first finding the value in between \'st\' and \'mid\', and then between \'mid + 1\' and \'en\'. \n\nThe values are calculated as follows:\n\n1. `seg[2 * ind + 1][1][0] + seg[2 * ind + 2][0][1]`: For the first block, we take 1, 0 because we have to ensure that the first index has been taken, and in the second block, we take 0, 1.\n2. `seg[2 * ind + 1][1][1] + seg[2 * ind + 2][0][1]`: After taking 1, 1 in the first block, we take 0, 1 in the second block. We can\'t take 1, 1 because non-adjacent elements can\'t be taken.\n3. `seg[2 * ind + 1][1][0] + seg[2 * ind + 2][1][1]`: Similar to the second case.\n\nBy finding all the possible combinations for the particular subarray, we can output the answer. This approach provides an optimal solution for finding the maximum in a subarray.\n\n# Complexity\n- Time complexity: O(nlogn)\n\n# Code\n```\nclass Solution {\npublic:\n    const int mod = 1e9 + 7;\n    const int inf = -2e9;\n    const static int N = 5e4 + 5;\n    long long seg[4 * N][2][2];\n    \n\n    void upd(int ind) {\n        seg[ind][1][1] = max({seg[2 * ind + 1][1][0] + seg[2 * ind + 2][1][1], seg[2 * ind + 1][1][0] + seg[2 * ind + 2][0][1], seg[2 * ind + 1][1][1] + seg[2 * ind + 2][0][1]});\n        seg[ind][1][0] = max({seg[2 * ind + 1][1][0] + seg[2 * ind + 2][1][0], seg[2 * ind + 1][1][0] + seg[2 * ind + 2][0][0], seg[2 * ind + 1][1][1] + seg[2 * ind + 2][0][0]});\n        seg[ind][0][1] = max({seg[2 * ind + 1][0][1] + seg[2 * ind + 2][0][1], seg[2 * ind + 1][0][0] + seg[2 * ind + 2][1][1], seg[2 * ind + 1][0][0] + seg[2 * ind + 2][0][1]});\n        seg[ind][0][0] = max({seg[2 * ind + 1][0][0] + seg[2 * ind + 2][1][0], seg[2 * ind + 1][0][0] + seg[2 * ind + 2][0][0], seg[2 * ind + 1][0][1] + seg[2 * ind + 2][0][0]});\n    }\n\n    void build(int ind, int st, int en, vector<int>& A) {\n        if(st == en) {\n            seg[ind][1][1] = A[st];\n            seg[ind][0][0] = 0;\n            seg[ind][0][1] = inf;\n            seg[ind][1][0] = inf;\n            return;\n        }\n        int mid = (st + en) >> 1;\n        build(2 * ind + 1, st, mid, A);\n        build(2 * ind + 2, mid + 1, en, A);\n        upd(ind);\n    }\n    \n    void update(int ind, int st, int en, int index, int with) {\n        if(st == en) {\n            seg[ind][1][1] = with;\n            return;\n        }\n        int mid = (st + en) >> 1;\n        if(mid >= index) {\n            update(2 * ind + 1, st, mid, index, with);\n        }\n        else {\n            update(2 * ind + 2, mid + 1, en, index, with);\n        }\n        upd(ind);\n    }\n\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        int n = nums.size();\n        build(0, 0, n - 1, nums);\n        long long ans = 0;\n        for(auto q : queries) {\n            int index = q[0];\n            int with = q[1];\n            update(0, 0, n - 1, index, with);\n            ans += max({seg[0][0][0], seg[0][0][1], seg[0][1][1], seg[0][1][0]});\n            ans %= mod;\n        }\n        return ans;\n    }\n};\n```
['Divide and Conquer', 'Dynamic Programming', 'Segment Tree', 'C++']