Iterative Solution
Intuition\niterative segment tree\n\n# Approach\niterative segment tree, with non commutative merging\n\n# Complexity\n- Time complexity:\nO(nlogn)\n\n- Space c
# Intuition\niterative segment tree\n\n# Approach\niterative segment tree, with non commutative merging\n\n# Complexity\n- Time complexity:\n`O(nlogn)`\n\n- Space complexity:\n`o(n)`\n\n# Code\n```\n\n#define MOD 1000000007\nstruct node {\n    int s1; // answer if ar is the last chosen element and al is the first chosen element\n    int s2; // answer if ar is the last chosen element and al-1 is the first chosen element\n    int e1; // answer if ar-1 is the last chosen element and al is the first chosen element\n    int e2; // answer if ar-1 is the last chosen element and al-1 is the first chosen element\n\n    node() : s1(0), s2(0), e1(0), e2(0){}\n    node(int s1, int s2, int e1, int e2) : s1(s1), s2(s2), e1(e1), e2(e2) {}\n};\n\nnode combine(const node& l, const node& r) {\n    node ans;\n\n    ans.s1 = max({l.s1 + r.s2, l.e1 + r.s1, l.e1 + r.s2});\n    ans.s2 = max({l.s2 + r.s2, l.e2 + r.s1, l.e2 + r.s2});\n    ans.e1 = max({l.s1 + r.e2, l.e1 + r.e1, l.e1 + r.e2});\n    ans.e2 = max({l.e2 + r.e2, l.e2 + r.e1, l.s2 + r.e2});\n    ans.s1%=MOD;\n    ans.s2%=MOD;\n    ans.e1%=MOD;\n    ans.e2%=MOD;\n    return ans;\n}\n\nvoid print(const node& l) {\n    cout << l.s1 << " " << l.s2 << " " << l.e1 << " " << l.e2  << endl;\n}\n\nclass Solution {\npublic:\n    int maximumSumSubsequence(vector<int>& a, vector<vector<int>>& queries) {\n        int n = a.size();\n        vector<node> tree(2 * n + 1, node(0, 0, 0, 0));\n\n        for (int i = 0; i < n; i++) {\n            tree[i + n] = node(a[i], 0, 0, 0);\n        }\n\n        for (int i = n - 1; i > 0; --i) {\n            tree[i] = combine(tree[i << 1], tree[i << 1 | 1]);\n        }\n\n        auto update = [&](int l, const node& upd) {\n            l += n;\n            tree[l] = upd;\n            print(tree[l]);\n            while (l > 1) {\n                l >>= 1;\n                tree[l] = combine(tree[l << 1], tree[l << 1 | 1]);\n            }\n        };\n\n        auto query = [&](int l, int r) -> int {\n            l += n;\n            r += n;\n            node ansl = node(-1, 0, 0, 0);\n            node ansr = node(-1, 0, 0, 0);\n            bool usedLeft = false, usedRight = false;\n\n            while (l < r) {\n                if (l & 1) {\n                    if (!usedLeft) {\n                        ansl = tree[l++];\n                        usedLeft = true;\n                    } else {\n                        ansl = combine(ansl, tree[l++]);\n                    }\n                }\n                if (r & 1) {\n                    if (!usedRight) {\n                        ansr = tree[--r];\n                        usedRight = true;\n                    } else {\n                        ansr = combine(tree[--r], ansr);\n                    }\n                }\n                l >>= 1;\n                r >>= 1;\n            }\n\n            node ans;\n            if (usedLeft && usedRight) ans = combine(ansl, ansr);\n            else if (usedLeft) ans = ansl;\n            else ans = ansr;\n            return max({ans.s1, ans.s2, ans.e1, ans.e2});\n        };\n\n        int sum = 0;\n        for (auto& c : queries) {\n            int l = c[0];\n            update(l, node(c[1], 0, 0, 0));\n            int x = query(0, n);\n            cout << x << endl;\n            sum += x;\n            sum%=MOD;\n        }\n        return sum;\n    }\n};\n\n```
['Segment Tree', 'C++']