c++ || Segment tree || Dynamic Programming
Intuition\n Describe your first thoughts on how to solve this problem. \nIntution came from  largest subarray sum in given range problem\n\n# Approach\n Describ
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIntution came from  largest subarray sum in given range problem\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nlook inside code\n\n# Complexity\n- Time complexity:\nN*log(N)\nN->size of array\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nH=ceil(log2(N));\nspace complexity=(pow(2,H+1)-1);\n\n# Code\n```\nconst int mod = 1e9 + 7;\nint mod_add(int a, int b) {\n    a = a % mod;\n    b = b % mod;\n    return (((a + b) % mod) + mod) % mod;\n}\nint const N = 5 * 1e4;\nint a[N + 2];\nint tree[4 * N + 2][2][2];\n\nvoid construct(int node, int l, int r) {\n    if (l == r) {\n        tree[node][0][0] = 0;\n        tree[node][0][1] = 0;\n        tree[node][1][0] = 0;\n        tree[node][1][1] = a[l];\n\n        return;\n    }\n\n    int mid = (l + r) / 2;\n    construct(2 * node, l, mid);\n    construct(2 * node + 1, mid + 1, r);\n\n    tree[node][0][0] =\n        max(tree[2 * node][0][1] + tree[2 * node + 1][0][0],\n            tree[2 * node][0][0] +\n                max(tree[2 * node + 1][0][0], tree[2 * node + 1][1][0]));\n    tree[node][0][1] =\n        max(tree[2 * node][0][1] + tree[2 * node + 1][0][1],\n            tree[2 * node][0][0] +\n                max(tree[2 * node + 1][0][1], tree[2 * node + 1][1][1]));\n    tree[node][1][0] =\n        max(tree[2 * node][1][1] + tree[2 * node + 1][0][0],\n            tree[2 * node][1][0] +\n                max(tree[2 * node + 1][0][0], tree[2 * node + 1][1][0]));\n    if (l + 1 < r)\n        tree[node][1][1] =\n            max(tree[2 * node][1][1] + tree[2 * node + 1][0][1],\n                tree[2 * node][1][0] +\n                    max(tree[2 * node + 1][0][1], tree[2 * node + 1][1][1]));\n    if (l + 1 == r)\n        tree[node][1][1] = 0;\n}\n\nint update(int node, int l, int r, int ind, int val) {\n    if (l == r) {\n        a[ind] = val;\n        tree[node][0][0] = 0;\n        tree[node][0][1] = 0;\n        tree[node][1][0] = 0;\n        tree[node][1][1] = a[l];\n\n        return max({tree[node][0][0], tree[node][0][1], tree[node][1][0],\n                    tree[node][1][1]});\n    }\n\n    int mid = (l + r) / 2;\n    int ans = 0;\n    if (ind <= mid) {\n        ans = max(ans, update(2 * node, l, mid, ind, val));\n    } else\n        ans = max(ans, update(2 * node + 1, mid + 1, r, ind, val));\n    tree[node][0][0] =\n        max(tree[2 * node][0][1] + tree[2 * node + 1][0][0],\n            tree[2 * node][0][0] +\n                max(tree[2 * node + 1][0][0], tree[2 * node + 1][1][0]));\n    tree[node][0][1] =\n        max(tree[2 * node][0][1] + tree[2 * node + 1][0][1],\n            tree[2 * node][0][0] +\n                max(tree[2 * node + 1][0][1], tree[2 * node + 1][1][1]));\n    tree[node][1][0] =\n        max(tree[2 * node][1][1] + tree[2 * node + 1][0][0],\n            tree[2 * node][1][0] +\n                max(tree[2 * node + 1][0][0], tree[2 * node + 1][1][0]));\n    if (l + 1 < r)\n        tree[node][1][1] =\n            max(tree[2 * node][1][1] + tree[2 * node + 1][0][1],\n                tree[2 * node][1][0] +\n                    max(tree[2 * node + 1][0][1], tree[2 * node + 1][1][1]));\n    if (l + 1 == r)\n        tree[node][1][1] = 0;\n\n    return max({ans, tree[node][0][0], tree[node][0][1], tree[node][1][0],\n                tree[node][1][1]});\n}\n\nclass Solution {\npublic:\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& q) {\n        int sum = 0;\n        int n = nums.size();\n        memset(tree, 0, sizeof(tree));\n        for (int i = 0; i < nums.size(); i++) {\n            a[i + 1] = nums[i];\n        }\n\n        construct(1, 1, n);\n\n        int k = q.size();\n        for (int i = 0; i < k; i++) {\n            int ind = q[i][0];\n            int x = q[i][1];\n            int temp_sum = update(1, 1, n, ind + 1, x);\n\n            sum = mod_add(sum, temp_sum);\n        }\n        return sum;\n    }\n};\n```
['Divide and Conquer', 'Dynamic Programming', 'Segment Tree', 'C++']