Segment Tree | Java | Easy to Understand
\nclass Solution {\n    int mod = (int)1e9+7;\n    public int maximumSumSubsequence(int[] nums, int[][] queries) {\n        SegmentTree sg = new SegmentTree(num
```\nclass Solution {\n    int mod = (int)1e9+7;\n    public int maximumSumSubsequence(int[] nums, int[][] queries) {\n        SegmentTree sg = new SegmentTree(nums);\n        long sum = 0;\n\n        for(int q[] : queries) {\n            sg.update(q[0], q[1]);\n            sum += sg.query(0, nums.length-1);\n            sum %= mod;\n        }\n        return (int)sum;\n    }\n}\n\nclass Node {\n\n    long sum, sumL, sumR, sumLR; \n    public Node(long n) {\n        sum = n;\n        sumL = sumR = sumLR = 0;\n        sum = Math.max(sum, 0);\n    }\n    \n    public static Node merge(Node left, Node right) {\n        Node res = new Node(0);\n        \n        // maxium sum\n        res.sum = Math.max(res.sum, left.sum);\n        res.sum = Math.max(res.sum, right.sum);\n        res.sum = Math.max(res.sum, left.sumR + right.sum);\n        res.sum = Math.max(res.sum, left.sum + right.sumL);\n        \n        // sumL = maxSum without Left most element\n        res.sumL = Math.max(res.sumL, left.sumL);\n        res.sumL = Math.max(res.sumL, right.sum);\n        res.sumL = Math.max(res.sumL, left.sumLR + right.sum);\n        res.sumL = Math.max(res.sumL, left.sumL + right.sumL);\n        \n        // sumR = maxSum without Right most element\n        res.sumR = Math.max(res.sumR, left.sum);\n        res.sumR = Math.max(res.sumR, right.sumR);\n        res.sumR = Math.max(res.sumR, left.sum + right.sumLR);\n        res.sumR = Math.max(res.sumR, left.sumR + right.sumR);\n        \n        //sumLR  = maxSum without Left most element and Right most element\n        res.sumLR = Math.max(res.sumLR, left.sumL);\n        res.sumLR = Math.max(res.sumLR, right.sumR);\n        res.sumLR = Math.max(res.sumLR, left.sumLR + right.sumR);\n        res.sumLR = Math.max(res.sumLR, left.sumL + right.sumLR);\n        \n        return res;\n    }\n}\n\nclass SegmentTree {\n    Node tree[];\n    int nums[];\n    int mod = (int)1e9+7;\n    \n    public SegmentTree(int []nums) {\n        this.nums = nums;\n        int n = nums.length;\n        tree = new Node[4*n+1];\n        buildTree(0, 0, n-1);\n    }\n    \n    void buildTree(int index, int left, int right) {\n        if(left > right) return;\n        if(left == right) {\n            tree[index] = new Node(nums[left]);\n            return;\n        }\n        \n        int mid = (left + right) / 2;\n        int leftIndex = 2*index+1;\n        int rightIndex = 2*index+2;\n        \n        buildTree(leftIndex, left, mid);\n        buildTree(rightIndex, mid+1, right);\n        \n        tree[index] = Node.merge(tree[leftIndex], tree[rightIndex]);\n    }\n    \n    long query(int l, int r) {\n        Node node = query(0, 0, nums.length-1, l, r);\n        return node.sum % mod;\n    }\n    \n    void update(int i, int val) {\n        nums[i] = val;\n        update(0, 0, nums.length-1, i, val);\n    }\n    \n    Node query(int i, int left, int right, int qLeft, int qRight) {\n        if(right < qLeft || left > qRight) return new Node(0); \n        if(right <= qRight && left >= qLeft) return tree[i];\n        \n        int mid = (left + right) / 2;\n        int li = 2*i+1;\n        int ri = 2*i+2;\n        \n        Node leftNode = query(li, left, mid, qLeft, qRight);\n        Node rightNode = query(ri, mid+1, right, qLeft, qRight);\n        return Node.merge(leftNode, rightNode);\n    }\n    \n     void update(int index, int left, int right, int tar, int val) {\n        if(left > right) return;\n        if(left == right) {\n            tree[index] = new Node(nums[left]);\n            return;\n        }\n        \n        int mid = (left + right) / 2;\n        int leftIndex = 2*index+1;\n        int rightIndex = 2*index+2;\n        \n         if(tar <= mid) update(leftIndex, left, mid, tar, val);\n         else update(rightIndex, mid+1, right, tar, val);\n        \n        tree[index] = Node.merge(tree[leftIndex], tree[rightIndex]);\n    }\n}\n```
['Tree', 'Java']