100% faster and space efficient 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)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\nstatic const int mod=1e9+7;\n    struct Node{\n        long nBE=0,nLE=0,nRE=0,iBE=0;\n    };\n    class SEGtree{\n        private:\n        Node* seg;\n        int n;\n        public:\n        SEGtree(int n){\n            this->n=n;\n            seg=new Node[4*n+1];\n        }\n        void build(int ind,int l,int r,vector<int>& arr){\n            if(l==r){\n                seg[ind].iBE=arr[l];\n                return;\n            }\n            int mid=l+((r-l)>>1);\n            build(2*ind+1,l,mid,arr);\n            build(2*ind+2,mid+1,r,arr);\n            Node* n1=&seg[2*ind+1];\n            Node* n2=&seg[2*ind+2]; \n            seg[ind].nBE=(max(n1->nLE+n2->nBE, n1->nBE+n2->nRE))%mod;\n            seg[ind].nLE=(max(n1->nLE+n2->nLE, n1->nBE+n2->iBE))%mod;\n            seg[ind].nRE=(max(n1->nRE+n2->nRE, n1->iBE+n2->nBE))%mod;\n            seg[ind].iBE=(max(n1->iBE+n2->nLE, n1->nRE+n2->iBE))%mod;\n        }\n        void update(int ind,int l,int r,int i,int val){\n            if(l==r){\n                seg[ind].iBE=max(0,val);\n                return;\n            }\n            int mid=l+((r-l)>>1);\n            if(i<=mid) update(2*ind+1,l,mid,i,val);\n            else update(2*ind+2,mid+1,r,i,val);\n            Node* n1=&seg[2*ind+1];\n            Node* n2=&seg[2*ind+2]; \n            seg[ind].nBE=(max(n1->nLE+n2->nBE, n1->nBE+n2->nRE))%mod;\n            seg[ind].nLE=(max(n1->nLE+n2->nLE, n1->nBE+n2->iBE))%mod;\n            seg[ind].nRE=(max(n1->nRE+n2->nRE, n1->iBE+n2->nBE))%mod;\n            seg[ind].iBE=(max(n1->iBE+n2->nLE, n1->nRE+n2->iBE))%mod;\n        }\n        int maxSubseqSum(){\n            return max(max(seg[0].iBE,seg[0].nBE),max(seg[0].nLE,seg[0].nRE));\n        }\n    };\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& qry) {\n        int n=nums.size();\n        int q=qry.size();\n        SEGtree* obj=new SEGtree(n);\n\n        obj->build(0,0,n-1,nums);\n        long ans=0;\n        for(int i=0;i<q;i++){\n            obj->update(0,0,n-1,qry[i][0],qry[i][1]);\n            ans+=obj->maxSubseqSum();\n            ans%=mod;\n        }\n        return ans;\n\n\n    }\n};\n```
['C++']