[C++] Segment tree with explanation.
The basic idea is from this codeforces blog.\n\nTime complexity : O(nlogn + qlogn)\n\n\nstruct node{\n    long long ans1,ans2,ans3,ans4;\n};\n\nconst int N = 50
The basic idea is from this codeforces [blog](https://codeforces.com/blog/entry/56681).\n\nTime complexity : O(nlogn + qlogn)\n\n```\nstruct node{\n    long long ans1,ans2,ans3,ans4;\n};\n\nconst int N = 50010;\nnode seg[4 * N];\nlong long a[N];\n\nvoid build(int l, int r, int pos){\n    if (l == r){\n        seg[pos].ans1 = a[l];\n        seg[pos].ans2 = 0;\n        seg[pos].ans3 = 0;\n        seg[pos].ans4 = 0;\n        return;\n    }\n\n    int mid = (l + r) / 2;\n    build(l, mid, pos * 2);\n    build(mid + 1, r, pos * 2 + 1);\n\n    seg[pos].ans1 = max({seg[pos*2].ans3+seg[pos*2+1].ans2,seg[pos*2].ans1+seg[pos*2+1].ans2,seg[pos*2].ans3+seg[pos*2+1].ans1});\n    seg[pos].ans2 = max({seg[pos*2].ans4+seg[pos*2+1].ans2,seg[pos*2].ans2+seg[pos*2+1].ans2,seg[pos*2].ans4+seg[pos*2+1].ans1});\n    seg[pos].ans3 = max({seg[pos*2].ans3+seg[pos*2+1].ans4,seg[pos*2].ans1+seg[pos*2+1].ans4,seg[pos*2].ans3+seg[pos*2+1].ans3});\n    seg[pos].ans4 = max({seg[pos*2].ans4+seg[pos*2+1].ans4,seg[pos*2].ans2+seg[pos*2+1].ans4,seg[pos*2].ans4+seg[pos*2+1].ans3});\n}\n\nvoid update(int pos){\n    seg[pos].ans1 = max({seg[pos*2].ans3+seg[pos*2+1].ans2,seg[pos*2].ans1+seg[pos*2+1].ans2,seg[pos*2].ans3+seg[pos*2+1].ans1});\n    seg[pos].ans2 = max({seg[pos*2].ans4+seg[pos*2+1].ans2,seg[pos*2].ans2+seg[pos*2+1].ans2,seg[pos*2].ans4+seg[pos*2+1].ans1});\n    seg[pos].ans3 = max({seg[pos*2].ans3+seg[pos*2+1].ans4,seg[pos*2].ans1+seg[pos*2+1].ans4,seg[pos*2].ans3+seg[pos*2+1].ans3});\n    seg[pos].ans4 = max({seg[pos*2].ans4+seg[pos*2+1].ans4,seg[pos*2].ans2+seg[pos*2+1].ans4,seg[pos*2].ans4+seg[pos*2+1].ans3});\n}\n\nvoid upd(int l, int r, int pos, int id, long long new_val){\n    if (l == r) {\n        a[l] = new_val;\n        seg[pos].ans1 = a[l];\n        seg[pos].ans2 = 0;\n        seg[pos].ans3 = 0;\n        seg[pos].ans4 = 0;\n    }\n    else {\n        int m = (l + r) / 2;\n        if (id <= m)\n            upd(l, m,pos*2, id, new_val);\n        else\n            upd(m+1, r,pos*2+1, id, new_val);\n        update(pos);\n    }\n}\n\n\nclass Solution {\npublic:\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        int n=nums.size();\n        for(int i=0;i<n;i++) a[i]=nums[i];\n        build(0,n-1,1);\n        long long ans=0,md=1e9+7;\n        for(auto p:queries){\n            int pos=p[0];\n            long long x=p[1];\n            upd(0,n-1,1,pos,x);\n            ans=(ans+max({seg[1].ans1,seg[1].ans2,seg[1].ans3,seg[1].ans4}))%md;\n        }\n        ans%=md;\n        return ans;\n    }\n};\n```
['Tree', 'C']