[Python 3] Segment tree
Intuition\nThe recipe comes from https://codeforces.com/blog/entry/56681\n\nEssentially, each segment tree node [lo, hi] keeps 4 quantities that stand for 4 dp 
# Intuition\nThe recipe comes from [https://codeforces.com/blog/entry/56681](https://codeforces.com/blog/entry/56681)\n\nEssentially, each segment tree node [lo, hi] keeps 4 quantities that stand for 4 dp states\n- lo and hi are selected in the sequence\n- lo not selected, lo + 1 and hi selected\n- lo selected, hi not selected, hi - 1 selected\n- lo and hi not selected, lo + 1 and hi - 1 selected\n\nEach query, we update a node\'s states from the states of its two children\n- `l0h0A, l1h0A, l0h1A, l1h1A` are the 4 states of its left child,\n- `l0h0B, l1h0B, l0h1B, l1h1B` are the 4 states of its right child,\n\nthen for then current node\n- `state[lo and hi] = max(l0h1A + l1h0B, l0h0A + l1h0B, l0h1A + l0h0B)`\n- `state[lo + 1 and hi] = max(l1h1A + l1h0B, l1h0A + l1h0B, l1h1A + l0h0B)`\n- `state[lo and hi - 1] = max(l0h1A + l1h1B, l0h0A + l1h1B, l0h1A + l0h1B)`\n- `state[lo + 1 and hi - 1] = max(l1h1A + l1h1B, l1h0A + l1h1B, l1h1A + l0h1B)`\n\nNote that leaf node value will never be set negative since we can always select an empty sequence, and do not forget to mod the final answer.\n\n# Code\n```\nclass Solution:\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        n = len(nums)\n        tree = [[0] * 4 for _ in range(4 * n)]\n        \n        def build(tidx, lo, hi):\n            if lo == hi:\n                tree[tidx][0] = max(0, nums[lo])\n            else:\n                mid = (lo + hi) // 2\n                build(2 * tidx + 1, lo, mid)\n                build(2 * tidx + 2, mid + 1, hi)\n                l0h0A, l1h0A, l0h1A, l1h1A = tree[2 * tidx + 1]\n                l0h0B, l1h0B, l0h1B, l1h1B = tree[2 * tidx + 2]\n                # lo to hi\n                tree[tidx][0] = max(l0h1A + l1h0B, l0h0A + l1h0B, l0h1A + l0h0B)\n                # lo + 1 to hi\n                tree[tidx][1] = max(l1h1A + l1h0B, l1h0A + l1h0B, l1h1A + l0h0B)\n                # lo to hi - 1\n                tree[tidx][2] = max(l0h1A + l1h1B, l0h0A + l1h1B, l0h1A + l0h1B)\n                # lo + 1 to hi - 1\n                tree[tidx][3] = max(l1h1A + l1h1B, l1h0A + l1h1B, l1h1A + l0h1B)\n        \n        build(0, 0, n - 1)\n        \n        def update(tidx, lo, hi, i, val):\n            if lo == hi:\n                tree[tidx][0] = max(0, val)\n            else:\n                mid = (lo + hi) // 2\n                if i > mid:\n                    update(tidx * 2 + 2, mid + 1, hi, i, val)\n                else:\n                    update(tidx * 2 + 1, lo, mid, i, val)\n                l0h0A, l1h0A, l0h1A, l1h1A = tree[2 * tidx + 1]\n                l0h0B, l1h0B, l0h1B, l1h1B = tree[2 * tidx + 2]\n                # lo to hi\n                tree[tidx][0] = max(l0h1A + l1h0B, l0h0A + l1h0B, l0h1A + l0h0B)\n                # lo + 1 to hi\n                tree[tidx][1] = max(l1h1A + l1h0B, l1h0A + l1h0B, l1h1A + l0h0B)\n                # lo to hi - 1\n                tree[tidx][2] = max(l0h1A + l1h1B, l0h0A + l1h1B, l0h1A + l0h1B)\n                # lo + 1 to hi - 1\n                tree[tidx][3] = max(l1h1A + l1h1B, l1h0A + l1h1B, l1h1A + l0h1B)\n        \n        ans = 0\n        for i, x in queries:\n            update(0, 0, n - 1, i, x)\n            ans += max(tree[0])\n        return ans % 1_000_000_007\n```\n\n2n tree implementation, need to patch size of nums to be power of 2, otherwise, some left child may cover ranges to the right of its right counterpart.\n\n```\nclass Solution:\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        n = len(nums)\n        m = 1 << (n.bit_length())\n        nums += [0] * (m - n)\n        n = m\n        tree = [[0] * 4 for _ in range(2 * n + 1)]\n\n        def update(i, x):\n            j = i + n\n            tree[j][0] = max(0, x)\n            while j:\n                j >>= 1\n                l0h0A, l1h0A, l0h1A, l1h1A = tree[2 * j]\n                l0h0B, l1h0B, l0h1B, l1h1B = tree[2 * j + 1]\n                # lo to hi\n                tree[j][0] = max(l0h1A + l1h0B, l0h0A + l1h0B, l0h1A + l0h0B)\n                # lo + 1 to hi\n                tree[j][1] = max(l1h1A + l1h0B, l1h0A + l1h0B, l1h1A + l0h0B)\n                # lo to hi - 1\n                tree[j][2] = max(l0h1A + l1h1B, l0h0A + l1h1B, l0h1A + l0h1B)\n                # lo + 1 to hi - 1\n                tree[j][3] = max(l1h1A + l1h1B, l1h0A + l1h1B, l1h1A + l0h1B)\n\n        for i, x in enumerate(nums):\n            update(i, x)\n\n        ans = 0\n        for i, x in queries:\n            update(i, x)\n            ans += max(tree[1])\n        return ans % 1_000_000_007\n```
['Python3']