[Segment Trees] Easy to understand Solution with Comments!
\n/*\nexplanation: Max sum of subsequence using segment trees, this solution using these trees to make incremental query updates to our builded seg trees, It ca
```\n/*\nexplanation: Max sum of subsequence using segment trees, this solution using these trees to make incremental query updates to our builded seg trees, It can be shown that for each node there could be 4 states, ie is left\none is included, right one is included/excluded.. We combine nodes by having different cases, for example to combine two child nodes, we will take their states such that the left child node rightmost and right child mode leftest cannot be taken simultaneously, Using such there are 4 different config.\n\nTime & Space Complexity: O(n + qlogn) & O(n): Since segment tree build takes linear time and space, while also each query updation takes logn time, therefore its time and space complexity are n+qlogn and n respectively.\n*/\nclass SegmentTreeNode {\n    int[][] s;\n    int l;\n    int r;\n    SegmentTreeNode leftNode;\n    SegmentTreeNode rightNode;\n    \n    SegmentTreeNode(int l, int r) {\n        s = new int[2][2];\n        this.l = l;\n        this.r = r;\n        leftNode = null;\n        rightNode = null;\n    }\n    \n    String getObjectiveString() {\n        return String.format("[00]=%s, [01]=%s, [10]=%s, [11]=%s", s[0][0], s[0][1], s[1][0], s[1][1]);\n    }\n    \n    @Override\n    public String toString() {\n        String lnodestr = "";\n        String rnodestr = "";\n        if (leftNode != null) {\n            lnodestr = leftNode.toString();\n        }\n        if (rightNode != null) {\n            rnodestr = rightNode.toString();\n        }\n        String mystr = String.format("l: %s, r: %s, obj: <%s>, {lNode: %s, rNode: %s}", l, r, getObjectiveString(), lnodestr, rnodestr);\n\n        return mystr;\n    }\n}\n\nclass Solution {\n    long MODULO = (long)(1e9 + 7);\n\n    int max(long a, long b, long c) {\n        return (int)(Math.max(a, Math.max(b, c)) % MODULO);\n    }\n\n    void setObjectives(SegmentTreeNode n, SegmentTreeNode l, SegmentTreeNode r) {\n        // Use child l and child r nodes to set objectives to current node :)\n        n.s[1][1] = max(\n            l.s[1][0] + r.s[0][1],\n            l.s[1][1] + r.s[0][1],\n            l.s[1][0] + r.s[1][1]\n        );\n        \n        n.s[0][1] = max(\n            l.s[0][0] + r.s[1][1],\n            l.s[0][0] + r.s[0][1],\n            l.s[0][1] + r.s[0][1]\n        );\n        \n        n.s[1][0] = max(\n            l.s[1][0] + r.s[0][0],\n            l.s[1][0] + r.s[1][0],\n            l.s[1][1] + r.s[0][0]\n        );\n        \n        n.s[0][0] = max(\n            l.s[0][0] + r.s[0][0],\n            l.s[0][1] + r.s[0][0],\n            l.s[0][0] + r.s[1][0]\n        );\n    }\n    \n    SegmentTreeNode buildTree(int l, int r, int[] nums) {\n        if (l == r) {\n            // Single tree node, simple give default one\n            SegmentTreeNode node = new SegmentTreeNode(l, r);\n            node.s[0][0] = 0;\n            node.s[1][1] = nums[l];\n            node.s[0][1] = -1000000;\n            node.s[1][0] = -1000000;\n            return node;\n        }\n        \n        SegmentTreeNode leftNode = buildTree(l, (l+r)/2, nums);\n        SegmentTreeNode rightNode = buildTree(((l+r)/2)+1, r, nums);\n\n        SegmentTreeNode node = new SegmentTreeNode(l, r);\n        node.leftNode = leftNode;\n        node.rightNode = rightNode;\n        setObjectives(node, leftNode, rightNode);\n        \n        return node;\n    }\n    \n    void incrementalUpdate(SegmentTreeNode root, int pos, int value) {\n        if (root.l == root.r && root.r == pos) {\n            // We reach the culprit, the rootest node :)\n            root.s[1][1] = value; // Set value thus!\n            return;\n        }\n                \n        // Find which node should we go to\n        if (pos >= root.leftNode.l && pos <= root.leftNode.r) {\n            // Go left :)\n            incrementalUpdate(root.leftNode, pos, value);\n        } else {\n            incrementalUpdate(root.rightNode, pos, value);\n        }\n        \n        // At the end, we assume things are updated, so simply update root value!\n        setObjectives(root, root.leftNode, root.rightNode);\n    }\n    \n    public int getMaxObjective(SegmentTreeNode n) {\n        return Math.max(\n            Math.max(n.s[0][0], n.s[0][1]),\n            Math.max(n.s[1][0], n.s[1][1])\n        );\n    }\n\n    public int maximumSumSubsequence(int[] nums, int[][] queries) {\n        SegmentTreeNode root = buildTree(0, nums.length-1, nums);\n        // System.out.println(root);\n\n        long ans = 0;\n        // Now for each query, we even have to update things up :)\n        for (int[] q : queries) {\n            incrementalUpdate(root, q[0], q[1]);\n            ans += getMaxObjective(root) % MODULO;\n        }\n        \n        return (int)(ans % MODULO);\n    }\n}\n```
['Java']