Segment Tree
Intuition\nUse segment tree. On each node that covers nums[i..j], store 4 values:\n\nnn: max subseq sum without using nums[i] or nums[j]\nny: max subseq sum wit
# Intuition\nUse segment tree. On each node that covers `nums[i..j]`, store 4 values:\n```\nnn: max subseq sum without using nums[i] or nums[j]\nny: max subseq sum without using nums[i] but with nums[j]\nyn: max subseq sum with nums[i] but without nums[j]\nyy: max subseq sum using both nums[i] and nums[j]\n```\nbase case:\n```\nif i == j:\n    nn, ny, yn, yy = [0, -inf, -inf, nums[i]]\n```\nTo combine 2 adjacent subarrs `nums[i..j]` and `nums[j..k]`, just enumerate whether we use `nums[i]` and `nums[k]`:\n```\ndef combine(self, res1, res2):\n    nn1, ny1, yn1, yy1 = res1\n    nn2, ny2, yn2, yy2 = res2\n    nn = max(nn1 + yn2, nn1 + nn2, ny1 + nn2)\n    ny = max(nn1 + yy2, nn1 + ny2, ny1 + ny2)\n    yn = max(yn1 + yn2, yn1 + nn2, yy1 + nn2)\n    yy = max(yn1 + yy2, yn1 + ny2, yy1 + ny2)\n    return [nn, ny, yn, yy]\n```\nThe rest is routine segment tree operations.\n\nThen simply go through each query and do the update.\n\nComplexity: O(mlogn) where `m = len(query)` and `n = len(nums)`\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```\ninf = -float(\'inf\')\nclass SegTree:\n    def __init__(self, nums):\n        n = len(nums)\n        # each element: [nn, ny, yn, yy]\n        self.ar = [None] * (4*n+1)\n        self.build(0, 0, n-1, nums)\n    \n    def combine(self, t1, t2):\n        nn1, ny1, yn1, yy1 = t1\n        nn2, ny2, yn2, yy2 = t2\n        nn = max(nn1 + yn2, nn1 + nn2, ny1 + nn2)\n        ny = max(nn1 + yy2, nn1 + ny2, ny1 + ny2)\n        yn = max(yn1 + yn2, yn1 + nn2, yy1 + nn2)\n        yy = max(yn1 + yy2, yn1 + ny2, yy1 + ny2)\n        return [nn, ny, yn, yy]\n    \n    def build(self, i, l, r, nums):\n        if l == r:\n            self.ar[i] = [0, inf, inf, nums[l]]\n        else:\n            m = (l+r) // 2\n            self.build(2*i+1, l, m, nums)\n            self.build(2*i+2, m+1, r, nums)\n            self.ar[i] = self.combine(self.ar[2*i+1], self.ar[2*i+2])\n        \n    def update_v(self, i, l, r, idx, v):\n        if l == r and l == idx:\n            self.ar[i] = [0, inf, inf, v]\n        else:\n            m = (l+r)//2\n            if m < idx:\n                self.update_v(2*i+2, m+1, r, idx, v)\n            else:\n                self.update_v(2*i+1, l, m, idx, v)\n            self.ar[i] = self.combine(self.ar[2*i+1], self.ar[2*i+2])\n\nclass Solution:\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        M = 10**9 + 7\n        st = SegTree(nums)\n        n = len(nums)\n        res = 0\n        # print(st.ar)\n        for p, v in queries:\n            st.update_v(0, 0, n-1, p, v)\n            # print(st.ar)\n            res += max(st.ar[0])\n            res %= M\n        return res\n```
['Segment Tree', 'Python3']