Just a segment tree's good question
\n\n# Complexity\n- Time complexity:O(n+qlogn)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(2n+q*logn)\n Add your space complexity here, 
\n\n# Complexity\n- Time complexity:O(n+q*logn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(2*n+q*logn)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#define ll long long\nclass segnode{\n  public:\n    ll lr,l1r,lr1,l1r1;\n    segnode(){\n\n    }\n    \n    segnode(int lr,int l1r,int lr1,int l1r1){\n        this->lr=lr;\n        this->l1r=l1r;\n        this->lr1=lr1;\n        this->l1r1=l1r1;\n    }\n};\nclass SegmentTree{\n   \nvector<segnode> sgtree;\n\n  public:\n \n  SegmentTree(int n){\n     sgtree.resize(4*n+1);\n      \n      for(int i=0;i<4*n+1;i++){\n          segnode sgn; \n          sgtree[i]=sgn;\n               \n      }\n  }\n \n \n void build(int index,int low,int high,vector<int> &arr){\n     if(low==high){\n         sgtree[index]=segnode(arr[low],0,0,0);\n         return ;\n     }\n     \n     \n     \n     int mid=(low+high)/2;\n     \n     build(2*index+1,low,mid,arr);\n     build(2*index+2,mid+1,high,arr);\n     \n     sgtree[index].lr=max({sgtree[2*index+1].lr+sgtree[2*index+2].l1r,sgtree[2*index+1].lr1+sgtree[2*index+2].lr,sgtree[2*index+1].lr1+sgtree[2*index+2].l1r});\n     \n     sgtree[index].lr1=max({sgtree[2*index+1].lr+sgtree[2*index+2].l1r1,sgtree[2*index+1].lr1+sgtree[2*index+2].lr1,sgtree[2*index+1].lr1+sgtree[2*index+2].l1r1});\n     \n     \n     sgtree[index].l1r=max({sgtree[2*index+1].l1r+sgtree[2*index+2].l1r,sgtree[2*index+1].l1r1+sgtree[2*index+2].lr,sgtree[2*index+1].l1r1+sgtree[2*index+2].l1r});\n     \n     sgtree[index].l1r1=max({sgtree[2*index+1].l1r+sgtree[2*index+2].l1r1,sgtree[2*index+1].l1r1+sgtree[2*index+2].lr1,sgtree[2*index+1].l1r1+sgtree[2*index+2].l1r1});\n     \n     \n }\n \n int query(){\n    return max({sgtree[0].lr,sgtree[0].lr1,sgtree[0].l1r,sgtree[0].l1r1});\n }\n \n void update(int index,int low,int high,int i,int val){\n     if(low==high){\n         if(low==high){\n         sgtree[index]=segnode(val,0,0,0);\n         return ;\n     }\n     \n     }\n     \n     int mid=(low+high)/2;\n     \n     if(i<=mid)\n     update(2*index+1,low,mid,i,val);\n     \n     else\n     update(2*index+2,mid+1,high,i,val);\n     \n    sgtree[index].lr=max({sgtree[2*index+1].lr+sgtree[2*index+2].l1r,sgtree[2*index+1].lr1+sgtree[2*index+2].lr,sgtree[2*index+1].lr1+sgtree[2*index+2].l1r});\n     \n     sgtree[index].lr1=max({sgtree[2*index+1].lr+sgtree[2*index+2].l1r1,sgtree[2*index+1].lr1+sgtree[2*index+2].lr1,sgtree[2*index+1].lr1+sgtree[2*index+2].l1r1});\n     \n     \n     sgtree[index].l1r=max({sgtree[2*index+1].l1r+sgtree[2*index+2].l1r,sgtree[2*index+1].l1r1+sgtree[2*index+2].lr,sgtree[2*index+1].l1r1+sgtree[2*index+2].l1r});\n     \n     sgtree[index].l1r1=max({sgtree[2*index+1].l1r+sgtree[2*index+2].l1r1,sgtree[2*index+1].l1r1+sgtree[2*index+2].lr1,sgtree[2*index+1].l1r1+sgtree[2*index+2].l1r1});\n }\n};\nclass Solution {\npublic:\n    int mod=1e9+7;\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        SegmentTree sg(nums.size());\n        \n        sg.build(0,0,nums.size()-1,nums);\n        \n        ll ans=0;\n        \n        for(auto i:queries){\n            sg.update(0,0,nums.size()-1,i[0],i[1]);\n            ans=(ans%mod+(sg.query())%mod)%mod;\n        }\n        \n        return ans;\n    }\n};\n```
['Binary Indexed Tree', 'Segment Tree', 'C++']