Optimised Solution | Segment Tree | EasyOne | C++
Intuition\n use segment trees, for any range maintain 4 types of values -\n1. maximum possible sum we can get if we include both the leftmost and rightmost elem
# Intuition\n use segment trees, for any range maintain 4 types of values -\n1. maximum possible sum we can get if we include both the leftmost and rightmost element.\n\n2. maximum possible sum excluding the leftmost element and including the rightmost element \n\n3. maximum possible sum excluding the rightmost element and including the leftmost element.\n\n4. maximum possible sum excluding both leftmost and rightmost element.\n\n# Approach\nmerge function has all the required calculations.\n\n# Complexity\n- Time complexity:\nO(nlogn)\n\n- Space complexity:\nO(n)\n\n# Code\n```\n int MOD = 1e9 + 7;\n\nstruct SegmentTreeNode {\n    long long sum_exclude_last;\n    long long sum_exclude_first;\n    long long exclude_f_l;\n    long long max_sum;\n    \n    SegmentTreeNode() : sum_exclude_last(0), exclude_f_l(0), sum_exclude_first(0), max_sum(0) {}\n    SegmentTreeNode(long long val) : sum_exclude_last(0),exclude_f_l(0), sum_exclude_first(0), max_sum(max(0LL,val)) {}\n};\n\nclass SegmentTree {\nprivate:\n    int n;\n    vector<SegmentTreeNode> tree;\n    \n    SegmentTreeNode merge( SegmentTreeNode& left,  SegmentTreeNode& right) {\n        SegmentTreeNode result;\n        result.sum_exclude_last = max({ 0LL, left.sum_exclude_last, left.sum_exclude_last + right.sum_exclude_last, left.max_sum + right.exclude_f_l, right.sum_exclude_last});\n        result.sum_exclude_first = max({0LL, right.sum_exclude_first, left.sum_exclude_first, right.sum_exclude_first + left.sum_exclude_first,  right.max_sum + left.exclude_f_l, right.max_sum });\n        result.max_sum = max({0LL, result.sum_exclude_last,result.sum_exclude_first,left.max_sum + right.sum_exclude_first, left.sum_exclude_last + right.max_sum, left.max_sum, right.max_sum, left.sum_exclude_last + right.sum_exclude_last , right.sum_exclude_first + left.sum_exclude_first, right.sum_exclude_first + left.sum_exclude_last});\n        result.exclude_f_l = max({0LL, left.exclude_f_l+right.sum_exclude_last, right.exclude_f_l+left.sum_exclude_first });\n        return result;\n    }\n    SegmentTreeNode merge2( SegmentTreeNode& left,  SegmentTreeNode& right) {\n        SegmentTreeNode result;\n        result.sum_exclude_last = max({ 0LL, left.max_sum});\n        result.sum_exclude_first = max({0LL, right.max_sum });\n        result.max_sum = max({0LL,left.max_sum , right.max_sum});\n        result.exclude_f_l = 0LL;\n        return result;\n    }\n    \n    void build( vector<int>& nums, int node, int start, int end) {\n        if (start == end) {\n            tree[node] = SegmentTreeNode(nums[start]);\n        } else {\n            int mid = (start + end) / 2;\n            build(nums, 2 * node + 1, start, mid);\n            build(nums, 2 * node + 2, mid + 1, end);\n\n            if( end - start == 1 )\n                tree[node] = merge2(tree[2 * node + 1], tree[2 * node + 2]);\n            else\n                tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);\n        }\n    }\n    \n    void update(int idx, int value, int node, int start, int end) {\n        if (start == end) {\n            tree[node] = SegmentTreeNode(value);\n        } else {\n            int mid = (start + end) / 2;\n            if (idx <= mid) {\n                update(idx, value, 2 * node + 1, start, mid);\n            } else {\n                update(idx, value, 2 * node + 2, mid + 1, end);\n            }\n\n            if( end - start == 1 )\n                tree[node] = merge2(tree[2 * node + 1], tree[2 * node + 2]);\n            else\n                tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);\n        }\n    }\n\n\npublic:\n    SegmentTree( vector<int>& nums) {\n        n = nums.size();\n        tree.resize(4 * n);\n        build(nums, 0, 0, n - 1);\n    }\n    \n    void update(int idx, int value) {\n        update(idx, value, 0, 0, n - 1);\n    }\n    \n    long long query() {\n        return tree[0].max_sum;\n    }\n};\n\n\nclass Solution {\npublic:\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& q) {\n        SegmentTree segTree(nums);\n\n        long long result = 0;\n\n        for (int i = 0; i < q.size(); ++i) {\n            int pos = q[i][0], value = q[i][1];\n            \n            segTree.update(pos, value);\n            int ans  = segTree.query();\n            // cout<<ans<<endl;\n            result = (result + ans) % MOD;\n        }\n\n        return result;\n\n    }\n};\n```
['Segment Tree', 'C++']