Segment Tree
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->O(N+QllogN)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->O(4*N)\n\n# Code\n```\n\nclass Solution {\npublic:\nvoid build(vector<vector<long long>>&seg,vector<int>&vec,int ind,int l,int r){\n    if(l==r){\n        seg[ind][0]=max(0,vec[l]);\n        seg[ind][1]=0;//excluding right\n        seg[ind][2]=0;//excluding left\n        seg[ind][3]=0;\n        return ;\n    }\n    int mid=l+(r-l)/2;\n    build(seg,vec,2*ind+1,l,mid);\n    build(seg,vec,2*ind+2,mid+1,r);\n    seg[ind][0]=max({seg[2*ind+1][1]+seg[2*ind+2][0],seg[2*ind+1][0]+seg[2*ind+2][2]});\n    seg[ind][1]=max({seg[2*ind+1][0]+seg[2*ind+2][3],seg[2*ind+1][1]+seg[2*ind+2][1]});\n    seg[ind][2]=max({seg[2*ind+1][2]+seg[2*ind+2][2],seg[2*ind+1][3]+seg[2*ind+2][0]});\n    seg[ind][3]=max({seg[2*ind+1][2]+seg[2*ind+2][3],seg[2*ind+1][3]+seg[2*ind+2][1]});\n} \nvector<long long> update(vector<vector<long long>>&seg,int ind,int l,int r,int p,int v){\n    if(l==r && r==p){\n        seg[ind][0]=max(0,v);\n        return seg[ind];\n    }\n    if(l>p||r<p) return {0,0,0,0};\n    int mid=l+(r-l)/2;\n    update(seg,2*ind+1,l,mid,p,v);\n    update(seg,2*ind+2,mid+1,r,p,v);\n    seg[ind][0]=max({seg[2*ind+1][1]+seg[2*ind+2][0],seg[2*ind+1][0]+seg[2*ind+2][2]});\n    seg[ind][1]=max({seg[2*ind+1][0]+seg[2*ind+2][3],seg[2*ind+1][1]+seg[2*ind+2][1]});\n    seg[ind][2]=max({seg[2*ind+1][2]+seg[2*ind+2][2],seg[2*ind+1][3]+seg[2*ind+2][0]});\n    seg[ind][3]=max({seg[2*ind+1][2]+seg[2*ind+2][3],seg[2*ind+1][3]+seg[2*ind+2][1]});\n    return seg[ind];\n}\n    const long long mod=1000000007;\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        int n=nums.size();\n        vector<vector<long long>>seg(4*n+5,vector<long long>(4));\n        build(seg,nums,0,0,n-1);\n        long long ans=0;\n        for(auto it:queries){\n            int a=it[0],b=it[1];\n            ans=(ans+update(seg,0,0,n-1,a,b)[0])%mod;\n            cout<<seg[0][0]<<" ";\n        }\n        return (int)ans;\n    }\n};\n```
['C++']