Segment Tree Sol
Intuition\nIn order to find max sum subsequence with no adjacent elements selected, maintain 4 values in every node of segment tree -> 4 combinations of whether
# Intuition\nIn order to find max sum subsequence with no adjacent elements selected, maintain 4 values in every node of segment tree -> `4 combinations of whether first el and last el is selected or not` in the max sum subsequence corrosponding to the range that the seg tree node represents.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n`T.C = O(Q * log N)`\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nusing ll = long long;\n#define lc (x << 1)\n#define rc (x << 1) | 1\nint N;\nvector<array<ll, 4>> ST;\n// 0 -> both first and last\n// 1 -> first but not last\n// 2 -> not first but last\n// 3 -> not first and not last\n\narray<ll, 4> combine(array<ll, 4> lcVal, array<ll, 4> rcVal)\n{\n    array<ll, 4> ans;\n    ans[0] = max(lcVal[0] + rcVal[2], lcVal[1] + max(rcVal[2], rcVal[0]));\n    ans[1] = max(lcVal[0] + rcVal[3], lcVal[1] + max(rcVal[1], rcVal[3]));\n    ans[2] = max(lcVal[2] + rcVal[2], lcVal[3] + max(rcVal[0], rcVal[2]));\n    ans[3] = max(lcVal[2] + rcVal[3], lcVal[3] + max(rcVal[1], rcVal[3]));\n    return ans;\n}\n\narray<ll, 4> query(int L, int R, int x = 1, int l = 1, int r = N + 1)\n{\n    // Base Case\n    if (l >= R or r <= L) return {0ll,0ll,0ll,0ll};\n    if (l >= L and r <= R) return ST[x];\n    int mid = (l + r) / 2;\n    // Combine\n    array<ll, 4> ans = combine(query(L, R, lc, l, mid), query(L, R, rc, mid, r));\n    return ans;\n}\n\nvoid update(int pos, int val, int x = 1, int l = 1, int r = N + 1)\n{\n    // no overlap\n    if (pos < l or pos >= r) return;\n    if (l == r - 1)\n    {\n        ST[x][0] = val;\n        ST[x][1] = ST[x][2] = ST[x][3] = 0;\n        return;\n    }\n    int mid = (l + r) / 2;\n    update(pos, val, lc, l, mid);\n    update(pos, val, rc, mid, r);\n\n    // pass the update information to ancestors\n    ST[x] = combine(ST[lc], ST[rc]);\n}\n\n\nclass Solution {\npublic:\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        \n        ll ans = 0;\n        int n = nums.size(); \n        N = n+1;\n        ST.assign(4*N, {0ll,0ll,0ll,0ll});\n        // 1-based indexed seg tree\n        for (int i=0; i<n; i++) update(i+1, nums[i]);\n        \n        for (auto q:queries)\n        {\n            int p = q[0], x = q[1];\n            update(p+1, x);\n            auto cur = query(1,n+1);\n            ans += max({cur[0], cur[1], cur[2], cur[3]});\n        }\n        return ans%1000000007;\n    }\n};\n```
['Segment Tree', 'C++']