Iterative Segment Tree || O(nlogn) || Cpp
Intuition\n Describe your first thoughts on how to solve this problem. \nNegative numbers doesn\'t contrinute in maximum sum. It\'s best to just replace them wi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nNegative numbers doesn\'t contrinute in maximum sum. It\'s best to just replace them with zeros. \nMain issue with the question is handling the updates. It may change the answer drastically  (completely new set of indexes of the array) so it is not possible to save this using some kind of prefix sum and all. Range query data-structures will handle the updates but how to merge the node?\n\n# Approach\nTo handle updates we will use a segment tree. Each node $$[l,r]$$ will contain the following:\n\n* answer if $$nums[r]$$ is the last chosen element and $$nums[l]$$ is the first chosen element\n* answer if $$nums[r]$$ is the last chosen element and $$nums[l+1]$$ is the first chosen element\n* answer if $$nums[r-1]$$ is the last chosen element and $$nums[l]$$ is the first chosen element\n* answer if $$nums[r-1]$$ is the last chosen element and $$nums[l+1]$$ is the first chosen element\n\nFor shorter notation I will use $$f(i,\u2009j)$$ as the answer if the first included element is $$num[i]$$ and the last is $$nums[j]$$. Then in other words in a node we will keep $$f(l,\u2009r)$$, $$f(l\u2009+\u20091,\u2009r)$$, $$f(l,\u2009r\u2009-\u20091)$$ and $$f(l\u2009+\u20091,\u2009r\u2009-\u20091)$$.\n\nNow the merging of two nodes can be done in constant time. Lets have two adjacent nodes $$(L_1,\u2009R_1)$$ and $$(L_2,\u2009R_2)$$. The conditions $$L1 \\le\u2009R1\u2009<\u2009L2\u2009\\le\u2009R2$$ and $$R_1\u2009+\u20091\u2009=\u2009L_1$$ hold. Then the merged node will have:\n\n$$ f(A,\u2009B)\u2009=\u2009max(f(A,\u2009R_1\u2009-\u20091)\u2009+\u2009f(L_2\u2009+\u20091,\u2009B),\u2009f(A,\u2009R_1)\u2009+\u2009f(L_2\u2009+\u20091,\u2009B),\u2009f(A,\u2009R_1\u2009-\u20091)\u2009+\u2009f(L_2,\u2009B)) $$\n\nWhere the pair $$(A,\u2009B)$$ is being one of the $$(L_1,\u2009R_2), (L_1\u2009+\u20091,\u2009R_2), (L_1,\u2009R_2\u2009-\u20091)$$  or $$(L_1\u2009+\u20091,\u2009R_2\u2009-\u20091)$$.\n\nAnd now the update is done by simply updating a leaf\'s node and the nodes from it to the root resulting in  complexity. The answer after each update will be the maximal of the 4 values for the root node.\n\nIn  the code $$l1$$ represent $$l+1$$ and $$r1$$ represents $$r-1$$\nUpdating the nodes by $$[nums[i],0,0,0]$$ cause only $$[l,r]$$ includes the node itself as $$ l=r=i $$ for the leaf nodes.\n\n**Source**: [codeforces blog link](https://codeforces.com/blog/entry/56681)\n\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#define ll long long\nstruct Tree {\n     typedef struct node{\n         ll lr,l1r,lr1,l1r1;\n     } T;\n     static constexpr T unit = {0, 0, 0, 0};\n     T f(T a, T b){\n          T res;\n          res.lr = max({a.lr1+b.l1r, a.lr+b.l1r,a.lr1+b.lr});\n          res.l1r = max({a.l1r1+b.l1r, a.l1r+b.l1r,a.l1r1+b.lr});\n          res.lr1 = max({a.lr1+b.l1r1, a.lr+b.l1r1,a.lr1+b.lr1});\n          res.l1r1 = max({a.l1r1+b.l1r1, a.l1r+b.l1r1,a.l1r1+b.lr1});\n          return res;\n     } // (any associative fn)\n     vector<T> s;\n     int n;\n     Tree(int n = 0, T def = unit): s(2 * n, def), n(n) {}\n     void update(int pos, T val) {\n          for (s[pos += n] = val; pos /= 2;)\n               s[pos] = f(s[pos * 2], s[pos * 2 + 1]);\n     }\n     T query(int b, int e) { // query [b, e)\n          T ra = unit, rb = unit;\n          for (b += n, e += n; b < e; b /= 2, e /= 2) {\n               if (b % 2) ra = f(ra, s[b++]);\n               if (e % 2) rb = f(s[--e], rb);\n          }\n          return f(ra, rb);\n     }\n};\n\n\nclass Solution {\npublic:\n    const int md=1e9+7;\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        int n=nums.size();\n        Tree T(n+1);\n        for(int i=0;i<n;i++){\n            if(nums[i]<0) nums[i]=0;\n            T.update(i,{nums[i],0,0,0});\n        }\n        ll ans=0;\n        for(auto q:queries){\n          ll ind=q[0],val=q[1];\n          if(val<0) val=0;\n          T.update(ind,{val,0,0,0});\n          auto res=T.query(0,n+1);\n          ll x=max({res.lr,res.l1r,res.lr1,res.l1r1});\n          ans=(ans+x)%md;\n        }\n        return ans;\n    }\n};\n```
['Segment Tree', 'C++']