Segtree (with explanation)
Approach\nWe can solve this problem using a segment tree. Each node corresponds to a range [L, R] and we\'re going to store 4 values - answers for [L,R],[L+1,R]
# Approach\nWe can solve this problem using a segment tree. Each node corresponds to a range `[L, R]` and we\'re going to store 4 values - answers for `[L,R],[L+1,R],[L,R-1],[L+1,R-1]`. Let\'s learn to combine them.\nFor two ranges `[A,L]` and `[R,B]`,\n`X[A,B]=max(X[A,L-1]+X[R+1,B], X[A,L]+X[R+1,B],X[A,L-1]+X[R,B])`\n`X[A+1,B]=ax(X[A+1,L-1]+X[R+1,B], X[A+1,L]+X[R+1,B],X[A+1,L-1]+X[R,B])`\n`X[A,B-1]=max(X[A,L-1]+X[R+1,B-1], X[A,L]+X[R+1,B-1],X[A,L-1]+X[R,B-1])`\n`X[A+1,B-1]=max(X[A+1,L-1]+X[R+1,B-1], X[A+1,L]+X[R+1,B-1],X[A+1,L-1]+X[R,B-1])`. All of these equations follow from the fact we cannot take two adjacent elements.\nFor leaf nodes, `X[A,A]=max(0, val)` while `X[A+1,A]=X[A,A-1]=X[A+1,A-1]=0`.\nThe answer for each query is going to be stored in the root node.\n\n# Complexity\n- Time complexity: $$O(qlogn)$$\n\n# Code\n```\n#include <iostream>\n#include <utility>\n#include <vector>\n#include <algorithm>\n#include <numeric>\n#include <map>\n#include <unordered_set>\n#include <iostream>\n#include <utility>\n#include <vector>\n#include <algorithm>\n#include <numeric>\n#include <map>\n#include <unordered_set>\n#include <unordered_map>\n#include <queue>\n#include <set>\n#include <stack>\n#include <fstream>\n#include <ext/pb_ds/assoc_container.hpp>\n#include <ext/pb_ds/tree_policy.hpp>\n#include <bitset>\n#include <sstream>\n#include <ext/rope>\n#include <ctime>\n#include <random>\n#include <cstdlib>\n#include <complex>\n\nusing namespace std;\nusing namespace __gnu_pbds;\nusing namespace __gnu_cxx;\n\n/* clang-format off */\n\n/* TYPES  */\n#define ll long long\n#define pii pair<int, int>\n#define pll pair<long long, long long>\n#define vi vector<int>\n#define vll vector<long long>\n#define vpii vector<pair<int, int>>\n#define vpii vector<pair<int, int>>\n#define vvpii vector<vector<pair<int, int>>>\n#define vpll vector<pair<long long, long long>>\n#define vvpll vector<vector<pair<long long, long long>>>\n#define vvi vector<vector<int>>\n#define vvll vector<vector<long long>>\n#define mii map<int, int>\n#define si set<int>\n#define sc set<char>\n\n\n\n/* FUNCTIONS */\n#define feach(el, v) for(auto &el: v)\n#define rep(i, n) for(int i=0;i<n;i++)\n#define reprv(i, n) for(int i=n-1;i>=0;i--)\n#define reps(i, s, e) for(int i=s;i<e;i++)\n#define reprve(i, e, s) for(int i=e;i>=s;i--)\n#define repe(x, y) for (auto &x: y)\n#define repe2(x, a, y) for (auto &[x,a]: y)\n\ntypedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> oSet;\n\nconst ll MOD = 1e9 + 7;\n\nstruct nd {\n    ll lr, lplus1r, lrminus1, lplus1rminus1;\n};\n\nnd combine (nd a, nd b) {\n    ll lr = max(a.lrminus1 + b.lplus1r, a.lr + b.lplus1r);\n    lr = max(lr, a.lrminus1 + b.lr);\n\n    ll lplus1r = max(a.lplus1rminus1 + b.lplus1r, a.lplus1r + b.lplus1r);\n    lplus1r = max(lplus1r, a.lplus1rminus1 + b.lr);\n\n    ll lrminus1 = max(a.lrminus1 + b.lplus1rminus1, a.lr + b.lplus1rminus1);\n    lrminus1 = max(lrminus1, a.lrminus1 + b.lrminus1);\n\n    ll lplus1rminus1 = max(a.lplus1rminus1 + b.lplus1rminus1, a.lplus1r + b.lplus1rminus1);\n    lplus1rminus1 = max(lplus1rminus1, a.lplus1rminus1 + b.lrminus1);\n\n    return {\n        lr % MOD, lplus1r % MOD, lrminus1 % MOD, lplus1rminus1 % MOD\n    };\n}\n\nclass Solution {\npublic:\n    void build(vector<nd> &stree, vi &vec, int v, int tl, int tr) {\n        if (tl == tr) {\n            stree[v] = {\n                    max(0, vec[tl]), 0, 0, 0\n            };\n            return;\n        }\n        int tm = (tl + tr) >> 1;\n        build(stree, vec, v << 1, tl, tm);\n        build(stree, vec, v << 1 | 1, tm + 1, tr);\n\n        stree[v] = combine(stree[v << 1], stree[v << 1 | 1]);\n    }\n\n    void update(vector<nd> &stree, int pos, int val, int v, int tl, int tr) {\n        if (tl == tr) {\n            stree[v] = {\n                    max(0, val), 0, 0, 0\n            };\n            return;\n        }\n\n        int tm = (tl + tr) >> 1;\n        if (pos <= tm) update(stree, pos, val, v << 1, tl, tm);\n        else update(stree, pos, val, v << 1 | 1, tm + 1, tr);\n\n        stree[v] = combine(stree[v << 1], stree[v << 1 | 1]);\n    }\n\n    ll query(vector<nd> &stree) {\n        ll ans = max(stree[1].lr, stree[1].lplus1r);\n        ans = max(ans, stree[1].lrminus1);\n        ans = max(ans, stree[1].lplus1rminus1);\n        return ans;\n    }\n\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        int n = nums.size();\n        vector<nd> segtree(4 * n);\n        build(segtree, nums, 1, 0, n - 1);\n\n        ll ans = 0;\n        int q = queries.size();\n        rep(i, q) {\n            ll pos = queries[i][0], x = queries[i][1];\n            update(segtree, pos, x, 1, 0, n - 1);\n            ans += query(segtree);\n            ans %= MOD;\n        }\n        return ans;\n    }\n};\n```
['C++']