segment tree solution, save mutiple vals for each tree node
Intuition\n Describe your first thoughts on how to solve this problem. \nsegment tree\n\n# Approach\n Describe your approach to solving the problem. \nuse segme
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nsegment tree\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nuse segment tree, after build the tree, each tree node has a range [start, end], and a val array [left, right, mid, both]\nleft: the max sum of subsequence for range [start, end-1]\nright: the max sum of subsequence for range [start+1, end]\nmid: the max sum of subsequence for range [start+1, end-1]\nboth: the max sum of subsequence for range [start, end]\n\ntree.query(i, j) return the val ([left, right, mid, both]) for the range [start=i, end=j]\n\nso for each query in queries, firstly update the segment tree , then the tree.query(0, N-1)[3] is the max sum of latest nums array\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(nlog(n))\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass TreeNode:\n    def __init__(self, start, end, val, left, right):\n        self.start = start\n        self.end = end\n        \n        # val not only save the [start,end] range val\n        # but also save other 3 cases, [start, end-1], [start+1, end], [start+1, end-1]\n        self.val = val # [left, right, mid, both]\n                       # left  -->  [start, end-1]\n                       # right -->  [start+1, end]\n                       # mid  -->  [start+1, end-1]\n                       # both -->  [start, end]\n        self.left = left\n        self.right = right\nclass SegmentTree:\n    def __init__(self, nums):\n        def build(nums, start, end):\n            if start == end:\n                val = [0, 0, 0, nums[start] if nums[start] > 0 else 0]\n                return TreeNode(start, end, val, None, None)\n            mid = start + (end - start) // 2\n            left = build(nums, start, mid)\n            right = build(nums, mid+1, end)\n            val_left = max(left.val[3]+right.val[2], left.val[0]+right.val[0])\n            val_right = max(left.val[1]+right.val[1], left.val[2]+right.val[3])\n            val_mid = max(left.val[1]+right.val[2], left.val[2]+right.val[0])\n            val_both = max(left.val[3]+right.val[1], left.val[0]+right.val[3])\n            val = [val_left, val_right, val_mid, val_both]\n            return TreeNode(start, end, val, left, right)\n\n        self.root = build(nums, 0, len(nums)-1)\n    def doQuery(self, node, start, end):\n        if start > end:\n            return 0\n        if node.start == start and node.end == end:\n            return node.val\n\n        mid = node.start + (node.end - node.start) // 2\n        if mid < start:\n            return self.doQuery(node.right, start, end)\n        elif mid >= end:\n            return self.doQuery(node.left, start, end)\n\n        left = self.doQuery(node.left, start, mid)\n        right = self.doQuery(node.right, mid+1, end)\n        val_left = max(left[3] + right[2], left[0] + right[0])\n        val_right = max(left[1] + right[1], left[2] + right[3])\n        val_mid = max(left[1] + right[2], left[2] + right[0])\n        val_both = max(left[3] + right[1], left[0] + right[3])\n        val = [val_left, val_right, val_mid, val_both]\n        return val\n\n    def query(self, start, end):\n        return self.doQuery(self.root, start, end)\n\n    def doUpdate(self, node, pos, val):\n        start, end = node.start, node.end\n        if start == end == pos:\n            node.val[3] = val\n            return\n\n        mid = start + (end - start) // 2\n        if pos > mid:\n            self.doUpdate(node.right, pos, val)\n        else:\n            self.doUpdate(node.left, pos, val)\n\n        left, right = node.left.val, node.right.val\n        val_left = max(left[3] + right[2], left[0] + right[0])\n        val_right = max(left[1] + right[1], left[2] + right[3])\n        val_mid = max(left[1] + right[2], left[2] + right[0])\n        val_both = max(left[3] + right[1], left[0] + right[3])\n        node.val = [val_left, val_right, val_mid, val_both]\n\n    def update(self, pos, val):\n        self.doUpdate(self.root, pos, val)\n\nclass Solution:\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        N = len(nums)\n        tree = SegmentTree(nums)\n        res, MOD = 0, 10**9+7\n        for query in queries:\n            tree.update(query[0], query[1] if query[1] > 0 else 0)\n            cur = tree.query(0, N-1)\n            res = (res + cur[3]) % MOD\n        return res\n\n\n```
['Segment Tree', 'Python3']