Segment Tree | OOP | O(NlogN + QlogN)
Intuition\nSegment Tree\n\nEasy to follow method names\n\n# Code\n\nimport java.util.Arrays;\n\nclass SegTree {\n    private class Record {\n        int TAKE_FI
# Intuition\nSegment Tree\n\nEasy to follow method names\n\n# Code\n```\nimport java.util.Arrays;\n\nclass SegTree {\n    private class Record {\n        int TAKE_FIRST_TAKE_LAST;\n        int TAKE_FIRST_SKIP_LAST;\n        int SKIP_FIRST_SKIP_LAST;\n        int SKIP_FIRST_TAKE_LAST;\n\n        public Integer getMax() {\n            return Arrays.asList(this.TAKE_FIRST_SKIP_LAST, this.TAKE_FIRST_TAKE_LAST, this.SKIP_FIRST_SKIP_LAST, this.SKIP_FIRST_TAKE_LAST)\n                    .stream().max(Integer::compare).orElse(null);\n        }\n\n        public Integer skipLast() {\n            return Arrays.asList(this.TAKE_FIRST_SKIP_LAST, this.SKIP_FIRST_SKIP_LAST)\n                    .stream().max(Integer::compare).orElse(null);\n        }\n\n        public Integer takeLast() {\n            return Arrays.asList(this.SKIP_FIRST_TAKE_LAST, this.TAKE_FIRST_TAKE_LAST)\n                    .stream().max(Integer::compare).orElse(null);\n        }\n    }\n\n    private static Record[] seg;\n    private static int[] nums;\n\n    public SegTree(int[] nums) {\n        this.nums = nums;\n        seg = new Record[4*nums.length];\n        for (int i=0; i < 4*nums.length; ++i) seg[i] = new Record();\n        build(0, nums.length - 1, 0);\n    }\n\n    private void build(int i, int j, int k) {\n        if (i == j) {\n            seg[k].TAKE_FIRST_TAKE_LAST = nums[i];\n            return;\n        }\n        int mid = (i + j) >> 1;\n        build(i, mid, 2*k + 1);\n        build(mid + 1, j, 2*k + 2);\n        merge(k);\n    }\n\n    // merge [2*k+1, 2*k+2] into k\n    private static void merge(int k) {\n        seg[k].TAKE_FIRST_SKIP_LAST = Math.max(\n                seg[2*k+1].TAKE_FIRST_SKIP_LAST + seg[2*k+2].skipLast(),\n                seg[2*k+1].TAKE_FIRST_TAKE_LAST + seg[2*k+2].SKIP_FIRST_SKIP_LAST\n        );\n\n        seg[k].TAKE_FIRST_TAKE_LAST = Math.max(\n                seg[2*k+1].TAKE_FIRST_SKIP_LAST + seg[2*k+2].takeLast(),\n                seg[2*k+1].TAKE_FIRST_TAKE_LAST + seg[2*k+2].SKIP_FIRST_TAKE_LAST\n        );\n\n        seg[k].SKIP_FIRST_TAKE_LAST = Math.max(\n                seg[2*k+1].SKIP_FIRST_SKIP_LAST + seg[2*k+2].takeLast(),\n                seg[2*k+1].SKIP_FIRST_TAKE_LAST + seg[2*k+2].SKIP_FIRST_TAKE_LAST\n        );\n\n        seg[k].SKIP_FIRST_SKIP_LAST = Math.max(\n                seg[2*k+1].SKIP_FIRST_SKIP_LAST + seg[2*k+2].skipLast(),\n                seg[2*k+1].SKIP_FIRST_TAKE_LAST + seg[2*k+2].SKIP_FIRST_SKIP_LAST\n        );\n    }\n\n    // child -> parent\n    public void update(int idx, int val) {\n        int i = 0, j = nums.length - 1, k = 0;\n        update(idx, val, k, i, j);\n    }\n\n    private static void update(int idx, int val, int k, int i, int j) {\n        if (i == j) {\n            seg[k].TAKE_FIRST_TAKE_LAST = val;\n            return;\n        }\n        int mid = (i + j) >> 1;\n        if (idx <= mid)\n            update(idx, val, 2 * k + 1, i, mid);\n        else\n            update(idx, val, 2 * k + 2, mid + 1, j);\n        merge(k);\n    }\n\n    public int getMax(){\n        return seg[0].getMax();\n    }\n}\n\nclass Solution {\n    static int MOD = 1_000_000_007;\n    public int maximumSumSubsequence(int[] A, int[][] Q) {\n        var n = A.length;\n        int ans = 0;\n        SegTree segTree = new SegTree(A);\n        for (int[] q: Q) {\n            int idx = q[0], val = q[1];\n            segTree.update(idx, val);\n            ans = (ans + segTree.getMax()) % MOD;\n        }\n        return ans;\n    }\n}\n```
['Segment Tree', 'Java']