Python | Segment Tree
Based on https://leetcode.com/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/solutions/5208917/segment-tree/\n# Code\n\nclass Node:\n    def __i
Based on https://leetcode.com/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/solutions/5208917/segment-tree/\n# Code\n```\nclass Node:\n    def __init__(self, lo, hi, nums):\n        self.lo = lo\n        self.hi = hi\n        self.selected = [[0]*2 for _ in range(2)]\n        if lo < hi:\n            mid = (lo + hi)//2\n            self.l = Node(lo, mid, nums)\n            self.r = Node(mid+1, hi, nums)\n            self.combine()\n        else:\n            self.selected[0][0] = 0\n            self.selected[0][1] = float(\'-inf\')\n            self.selected[1][0] = float(\'-inf\')\n            self.selected[1][1] = nums[lo]\n    def combine(self):\n        self.selected[0][0] = max(self.l.selected[0][0]+self.r.selected[0][0], self.l.selected[0][1]+self.r.selected[0][0],self.l.selected[0][0]+self.r.selected[1][0])\n        self.selected[0][1] = max(self.l.selected[0][0]+self.r.selected[0][1], self.l.selected[0][1]+self.r.selected[0][1],self.l.selected[0][0]+self.r.selected[1][1])\n        self.selected[1][0] = max(self.l.selected[1][0]+self.r.selected[0][0], self.l.selected[1][1]+self.r.selected[0][0],self.l.selected[1][0]+self.r.selected[1][0])\n        self.selected[1][1] = max(self.l.selected[1][0]+self.r.selected[0][1], self.l.selected[1][1]+self.r.selected[0][1],self.l.selected[1][0]+self.r.selected[1][1])\n    def update(self, i, x):\n        if i < self.lo or self.hi < i: return \n        if self.lo == self.hi:\n            self.selected[0][0] = 0\n            self.selected[1][1] = x\n            return\n        self.l.update(i, x)\n        self.r.update(i, x)\n        self.combine()\n\nclass Solution:\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        n = len(nums)\n        tree = Node(0,len(nums)-1,nums)\n        res = 0\n        MOD = 10**9+7\n        for i,x in queries:\n            tree.update(i,x)\n            res += max(max(tree.selected[0]), max(tree.selected[1]))\n            res %= MOD\n        return res\n```
['Python3']