[Python] Using SegTree from AtCoder library
Intuition\n Describe your first thoughts on how to solve this problem. \nBuild a segtree with each node composed of 4 range sums: (x00, x01, x10, x11) where i i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBuild a segtree with each node composed of 4 range sums: `(x00, x01, x10, x11)` where `i` in `xij` means whether the leftmost number in the range is contributing to the sum (`i=1`) or not (`i=0`). Likewise, `j` for the rightmost number in the range. The important thing is that the leaf node should be initialized as `(0, 0, 0, nums[i])` because we cannot take _just left or right half_ of a number. For the operation that merges two segments, see `op()` function in the code that avoids using two consecutive numbers at the boundary between segments.\n\n# Complexity\n- Time complexity: $O((N + Q) \\log N)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(N)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\nThe shown code does not run on LC platform as it is because I am using a third-party library (https://github.com/not522/ac-library-python). In order to run it, install the library locally by\n```\npip install git+https://github.com/not522/ac-library-python\n```\nand convert the code so that it is self-contained:\n```\npython -m atcoder [your-source-code] -o [single-combined-code]\n```\nThen paste the converted code, which is a bit lengthy, so I\'d rather include the pre-coverted code here for readability.\n\n```python3 []\nfrom typing import List\nfrom atcoder.segtree import SegTree                                             \n                                                                                \nclass Solution:\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        mod = 10**9 + 7\n\n        def op(x, y):\n            x00, x01, x10, x11 = x\n            y00, y01, y10, y11 = y\n            return (max(x00 + y00, x00 + y10, x01 + y00),  # x0* + y*0 except x01 + y10\n                    max(x00 + y01, x00 + y11, x01 + y01),  # x0* + y*1 except x01 + y11\n                    max(x10 + y00, x10 + y10, x11 + y00),  # x1* + y*0 except x11 + y10\n                    max(x10 + y01, x10 + y11, x11 + y01))  # x1* + y*1 except x11 + y11\n\n        seg = SegTree(op, (0, 0, 0, 0), [(0, 0, 0, num) for num in nums])\n\n        ans = 0\n        for i, x in queries:\n            seg.set(i, (0, 0, 0, x))\n            top = seg.all_prod()\n            ans += max(top)\n            ans %= mod\n        return ans\n```
['Python3']