6358 ms Beats 100.00% of users with Python3
Intuition\n Describe your first thoughts on how to solve this problem. \nTo efficiently update and query the maximum sum subsequence with non-adjacent elements,
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo efficiently update and query the maximum sum subsequence with non-adjacent elements, we can utilize a segment tree data structure. The segment tree will store information about the maximum sum subsequence in each segment of the input array.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Define a Node class to represent each node in the segment tree. Each node will store information about the maximum sum subsequence for the segment it represents.\n2. Implement the combine method in the Node class to update the maximum sum subsequence information based on its children.\n3. Implement the update method in the Node class to update the segment tree when a value in the input array is modified.\n4. Initialize the segment tree using the input array.\n5. Iterate through the queries and update the segment tree accordingly.\n6. Calculate the maximum sum subsequence from the root of the segment tree after each query and accumulate the result.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1. Building the segment tree requires O(n) time, where n is the length of the input array.\n2. Each update operation on the segment tree takes O(log n) time.\n3. Each query operation on the segment tree also takes O(log n) time.\n4. Therefore, the overall time complexity is O(n + q log n), where q is the number of queries.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n1. The segment tree requires O(n) space to store the nodes and their associated information.\n2. Other auxiliary variables require constant space.\n3. Thus, the overall space complexity is O(n).\n\n# Code\n```\nclass Node:\n    def __init__(self, nums, lo, hi):\n        self.lo = lo\n        self.hi = hi\n        self.selected = [[0, -float(\'inf\')], [-float(\'inf\'), -float(\'inf\')]]\n        \n        if lo < hi:\n            mid = (lo + hi) // 2\n            self.l = Node(nums, lo, mid)\n            self.r = Node(nums, mid + 1, hi)\n            self.combine()\n        else:\n            self.selected[1][1] = nums[lo]\n    \n    def combine(self):\n        self.selected[0][0] = max(self.l.selected[0][0] + self.r.selected[0][0], max(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], max(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], max(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], max(self.l.selected[1][1] + self.r.selected[0][1], self.l.selected[1][0] + self.r.selected[1][1]))\n\n    def update(self, i, x):\n        if i < self.lo or i > self.hi:\n            return\n        \n        if self.lo == self.hi:\n            self.selected[0][0] = 0\n            self.selected[1][1] = x\n            return\n        \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        segmentTree = Node(nums, 0, len(nums) - 1)\n\n        res = 0\n        for query in queries:\n            segmentTree.update(query[0], query[1])\n            res += max(segmentTree.selected[0][0], max(segmentTree.selected[0][1], max(segmentTree.selected[1][0], segmentTree.selected[1][1])))\n            res %= 10**9 + 7\n        return res\n\n```\n\n# Upvote if it helped you!! Thank you!!
['Python3']