Divide and Conquer --- others call it segement tree
Intuition\nNaive Dynamic Programming solves the static question in O(n^2) time. However, we have O(n) query and doing dp everytime the list updates will cost to
# Intuition\nNaive Dynamic Programming solves the static question in O(n^2) time. However, we have O(n) query and doing dp everytime the list updates will cost too much time. Thus trying to do a lazy dp: do not compute all the results, instead, compute partial results, and combine them \nper query. \n\n# Approach\nUsing divide and conquer. I noticed other solutions call this methods segment tree. I simple think this is just solving the dp by divide and conquer: do not compute all the results, but compute the results of the first half, and the second half, and combine them. When combine the results, one may find knowing the maximal sum of sub sequence is not enough --- by simply considering leave one out (leave the first or last one), one can reconstruct the best solution.\n\n\n# Complexity\n- Time complexity:\nConstructing takes linear time, precompute all the data also takes linear time. Update and query each time takes $O(log(n))$ time per query, and thus $O(nlog(n))$ \n\n- Space complexity:\nIt is tree --- linear space.\n\n# Code\n```\nclass Node:\n    def __init__(self,start,end):\n        self.l = start\n        self.r = end\n        self.n = end-start+1\n        self.left = None\n        self.right = None\n        \n        self.all = 0\n        self.left_loo = 0\n        self.right_loo = 0\n        self.both_loo = 0\n    \nclass QueryTree:\n    def __init__(self,nums):\n        self.nums = nums\n        self.root = self.build(0, len(nums)-1)\n        self.calc(self.root)\n        \n    def build(self,start,end):\n        if start == end:\n            return Node(start,end)\n        \n        mid = (start+end)//2\n        root = Node(start,end)\n        root.left = self.build(start,mid)\n        root.right = self.build(mid+1,end)\n        return root\n    \n    def calc(self,node):\n        if node is None:\n            return \n        \n        if node.n == 1:\n            node.all = max(self.nums[node.l],0)\n            node.left_loo = 0\n            node.right_loo = 0\n            node.both_loo = 0\n            return\n        \n        # node has at least two children\n        self.calc(node.left)\n        self.calc(node.right)\n        \n        node.all = max(node.left.all + node.right.left_loo, \n                       node.left.right_loo + node.right.all)\n        node.left_loo = max(node.left.left_loo + node.right.left_loo,\n                           node.left.both_loo + node.right.all)\n        node.right_loo = max(node.left.all + node.right.both_loo,\n                            node.left.right_loo + node.right.right_loo)\n        node.both_loo = max(node.left.left_loo + node.right.both_loo,\n                           node.left.both_loo + node.right.right_loo)   \n        \n    def query(self):\n        return self.root.all\n    \n    def update(self,i,x):\n        self.nums[i] = x\n        self.recalc(self.root,i)\n    \n    def recalc(self,node,i):\n        if node is None:\n            return \n        \n        if node.n == 1:\n            if node.l == i:\n                node.all = max(self.nums[i],0)\n            return \n        \n        if (i < node.l) or (i > node.r):\n            return \n        \n        if i <= node.left.r:\n            self.recalc(node.left,i)\n        if i >= node.right.l:\n            self.recalc(node.right,i)\n        \n        node.all = max(node.left.all + node.right.left_loo, \n                       node.left.right_loo + node.right.all)\n        node.left_loo = max(node.left.left_loo + node.right.left_loo,\n                           node.left.both_loo + node.right.all)\n        node.right_loo = max(node.left.all + node.right.both_loo,\n                            node.left.right_loo + node.right.right_loo)\n        node.both_loo = max(node.left.left_loo + node.right.both_loo,\n                           node.left.both_loo + node.right.right_loo)   \n\nclass Solution:\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        ans = []\n        qt = QueryTree(nums)\n        for i,x in queries:\n            qt.update(i,x)\n            ans.append(qt.query())\n        return sum(ans) % (10 ** 9 + 7)\n```
['Python3']