[Python] Segment Tree
Time Complexity: Build: O(12N) Query: O(8Q * log N)\nSpace Complexity: O(~4N)\n\n\nclass SegmentTree:\n    def __init__(self, n):\n        self.len = 1\n       
Time Complexity: `Build: O(12N) Query: O(8Q * log N)`\nSpace Complexity: `O(~4N)`\n\n```\nclass SegmentTree:\n    def __init__(self, n):\n        self.len = 1\n        while self.len < n:\n            self.len *= 2\n        self.tree = [[[0, 0], [0, 0]] for _ in range(0, 2 * self.len)]\n\t\t\n    def glue(self, l, r):        \n        \'\'\'\n               [2, 1, 2, 4]  [8, 3, 6, 5]\n          x00 = i        k   1-k       j\n          x01 = 0        k   1-k       1\n        \'\'\'\n        res = [[0, 0], [0, 0]]\n        for i in [0, 1]:\n            for j in [0, 1]:\n                for k in [0, 1]:\n                    res[i][j] = max(res[i][j], l[i][k] + r[1 - k][j])\n        return res\n        \n    def _build(self, v, n, x, lx, rx):\n        if rx - lx == 1:\n            if lx < n:\n                self.tree[x] = [[0, 0], [0, v[lx]]]\n            return\n        m = (lx + rx) // 2\n        self._build(v, n, 2 * x + 1, lx, m)\n        self._build(v, n, 2 * x + 2, m, rx)\n        self.tree[x] = self.glue(self.tree[2 * x + 1], self.tree[2 * x + 2])\n    def build(self, v, n):\n        self._build(v, n, 0, 0, self.len)\n    \n    def _set(self, i, v, x, lx, rx):\n        if rx - lx == 1:\n            self.tree[x] = [[0, 0], [0, v]]\n            return\n        m = (lx + rx) // 2\n        if i < m:\n            self._set(i, v, 2 * x + 1, lx, m)\n        else:\n            self._set(i, v, 2 * x + 2, m, rx)\n        self.tree[x] = self.glue(self.tree[2 * x + 1], self.tree[2 * x + 2])\n    \n    def set(self, i, v):\n        self._set(i, v, 0, 0, self.len)\n        \n    def _get(self, l, r, x, lx, rx):\n        if lx >= r or l >= rx:\n            return [[0, 0], [0, 0]]\n        if lx >= l and rx <= r:\n            return self.tree[x]\n        m = (lx + rx) // 2\n        left = self._get(l, r, 2 * x + 1, lx, m)\n        right = self._get(l, r, 2 * x + 2, m, rx)\n        return self.glue(left, right)\n    \n    def get(self, l, r):\n        return self._get(l, r, 0, 0, self.len)\n    \nclass Solution:\n    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n        n = len(nums)\n        st = SegmentTree(n)\n        st.build(nums, n)\n        ans, mod = 0, 10 ** 9 + 7\n        for q in queries:\n            st.set(q[0], q[1])\n            res = st.get(0, n)\n            ans += max(max(row) for row in res)\n            ans %= mod\n        return ans                \n```
['Python']