Python | Segment Tree | Simple Template
Intuition\nWe need to efficiently update the array and get the result.So we can use segment tree in this case\n\n# Approach\n- For segment tree to work we need 
# Intuition\nWe need to efficiently update the array and get the result.So we can use segment tree in this case\n\n# Approach\n- For segment tree to work we need to maintain results of partitions in such a way that we can merge smaller partitions and get the result for larger partitions.\n- while merging smaller partions we need to make sure of some conditions like if we choose rightmost element of 1st partition we cannot choose the leftmost element in the 2nd partition\n- To do so each node in our segment tree will store results of 4 intervals which are (l,r) (l+1,r) (l,r-1) (l+1,r-1)\n- These 4 intervals will help us to merge smaller partitions \n  e.g for merging partition A and B \n    if we choose A[l,r] then we must choose either B[l+1,r] or B[l+1,r-1]\n- Also we can take max(0,nums[i]) to ignore negative numbers while initializing and updating.\n\n\n\n# Complexity\n- Time complexity:O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(nlogn)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n\n```python []\nMOD = 10**9+7\nclass Solution:\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        def merge(a,b):\n            # [(l,r), (l+1,r), (l,r-1), (l+1,r-1)]\n            p = [0,0,0,0]\n            p[0] = max(a[0] + b[1], a[2] + b[0])\n            p[1] = max(a[1] + b[1], a[3] + b[0])\n            p[2] = max(a[2] + b[2], a[0] + b[3])\n            p[3] = max(a[3] + b[2], a[1] + b[3])\n            return p \n\n\n        n = len(nums)\n        vals = [ [max(0,nums[i]),0,0,0] for i in range(n) ]\n\n        st = SegmentTree(vals=vals, func=merge, null=[0,0,0,0])\n        res = 0 \n        for i,v in queries:\n            st.update(i, [max(0,v),0,0,0] )\n            res = (res + st.query(0,n-1)[0]) % MOD\n        return res \n\n```\n```SegmentTree []\nclass SegmentTree:\n    def __init__(self, vals, func, null):\n        tree = {}\n\n        def _build(l,r):\n            if l == r:\n                tree[l,r] = vals[l]\n                return tree[l,r]\n            m = (l+r) // 2\n            tree[l,r] = func(_build(l,m) , _build(m+1,r))\n            return tree[l,r]\n        \n\n        _build(0,len(vals)-1)\n        self.tree = tree \n        self.func = func \n        self.null = null\n        self.n = len(vals)\n    \n \n    def query(self,x,y):\n        tree = self.tree\n        func = self.func \n        null = self.null\n        n = self.n\n\n        def _query(l,r):\n            if r < x or y < l :\n                # no overlap (x,y)=(1,3)  (l,r)=(5,6)\n                return null \n            if x <= l and r <= y :\n                return tree[l,r]\n            m = (l+r) // 2\n            return func(_query(l,m) , _query(m+1,r))\n\n        return _query(0, n-1)\n\n\n    def update(self, index, val):\n        tree = self.tree\n        func = self.func \n        n = self.n\n        def _update(l,r):\n            if l == r == index :\n                tree[l,r] = val\n                return tree[l,r]\n            \n            m = (l+r) // 2\n            if index <= m :\n                _update(l,m)\n            else:\n                _update(m+1,r)\n\n            tree[l,r] = func(tree[l,m] , tree[m+1,r])\n        \n        _update(0,n-1)\n    \n```\n\n
['Segment Tree', 'Python3']