Easy Java Solution || Segment Trees || O(q*logn)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n\n    static long ans[][][];\n    static int n;\n    static int arr[];\n\n    static void buildTree(int l, int r, int idx){\n        if(l==r){\n            ans[idx][0][0] = 0;\n            ans[idx][0][1] = ans[idx][1][0] = -(long)(1e12);\n            ans[idx][1][1] = (long)arr[l];\n            return;\n        }\n\n        int mid = l+(r-l)/2;\n        int left = 2*idx+1;\n        int right = 2*idx+2;\n        buildTree(l,mid,left);\n        buildTree(mid+1,r,right);\n\n        ans[idx][0][0] = Math.max(ans[left][0][0]+ans[right][0][0],Math.max(ans[left][0][0]+ans[right][1][0],ans[left][0][1]+ans[right][0][0]));\n        ans[idx][0][1] = Math.max(ans[left][0][0]+ans[right][0][1],Math.max(ans[left][0][0]+ans[right][1][1],ans[left][0][1]+ans[right][0][1]));\n        ans[idx][1][0] = Math.max(ans[left][1][0]+ans[right][0][0],Math.max(ans[left][1][0]+ans[right][1][0],ans[left][1][1]+ans[right][0][0]));\n        ans[idx][1][1] = Math.max(ans[left][1][0]+ans[right][0][1],Math.max(ans[left][1][0]+ans[right][1][1],ans[left][1][1]+ans[right][0][1]));\n    }\n\n    static void update(int l, int r, int idx, int val, int pos){\n        if(l==r){\n            ans[idx][0][0] = 0;\n            ans[idx][0][1] = ans[idx][1][0] = -(long)(1e12);\n            ans[idx][1][1] = (long)val;\n            return;\n        }\n\n        int mid = l+(r-l)/2;\n        int left = 2*idx+1;\n        int right = 2*idx+2;\n        if(mid>=pos) update(l,mid,left,val,pos);\n        else update(mid+1,r,right,val,pos);\n\n        ans[idx][0][0] = Math.max(ans[left][0][0]+ans[right][0][0],Math.max(ans[left][0][0]+ans[right][1][0],ans[left][0][1]+ans[right][0][0]));\n        ans[idx][0][1] = Math.max(ans[left][0][0]+ans[right][0][1],Math.max(ans[left][0][0]+ans[right][1][1],ans[left][0][1]+ans[right][0][1]));\n        ans[idx][1][0] = Math.max(ans[left][1][0]+ans[right][0][0],Math.max(ans[left][1][0]+ans[right][1][0],ans[left][1][1]+ans[right][0][0]));\n        ans[idx][1][1] = Math.max(ans[left][1][0]+ans[right][0][1],Math.max(ans[left][1][0]+ans[right][1][1],ans[left][1][1]+ans[right][0][1]));\n    }\n    public int maximumSumSubsequence(int[] nums, int[][] q) {\n        long mod = (long)(1e9)+7;\n        arr = nums;\n        n = arr.length;\n        ans = new long[4*n][2][2];\n\n        buildTree(0,n-1,0);\n        long res = 0;\n        for(var a : q){\n            int pos = a[0];\n            int val = a[1];\n            update(0,n-1,0,val,pos);\n\n            long x = Math.max(ans[0][0][0],Math.max(ans[0][0][1],Math.max(ans[0][1][0],ans[0][1][1])))%mod;\n            res = (res+x)%mod;\n        }\n        return (int)res;\n    }\n}\n```
['Java']