[Javascript] Solve Sub-Problems with Segment Tree
Segment Tree is NO Different from Binary Tree\nSegment tree is just a fancy term. It is no different from a binary tree. The key idea behind segment tree is to 
# Segment Tree is NO Different from Binary Tree\nSegment tree is just a fancy term. It is no different from a binary tree. The key idea behind segment tree is to avoid re-computing many values *(where the $\\log(n)$ time complexity comes from)* if an update is made to the tree.\n\nHow to skip re-computation? Well, if we can solve a problem using divide and conquer - reduce the original problem to two sub-problems, and the update only applies to one of the sub-problems, we can avoid re-solving the other sub-problem which the update doesn\'t affect.\n\nWhy divide and conquer? Because segment tree is a binary tree and involves recursion.\n\n> When we have a dataset and there will be frequent updates to some data points in the dataset, segment tree is commonly used if we want to compute some aggregation of the dataset (e.g. min/max value of the dataset, range sum, etc.).\n\n# Approach\nI will divide the solution into two parts:\n\n1. Solve the **base problem** (given an array, find the subsequence with no adjacent elements that has the maximum sum) using divide and conquer\n2. Create a segment tree **where each update to a number in the array results in solving the base problem again** in $\\log(n)$ time complexity (the $\\log(n)$ time complexity comes for free when segment tree data structure is used)\n\n## How to Find Subsequence of Max Sum with No Adjacent Elements Using Divide and Conquer\nLet\'s look at an array:\n$$[x_1,\\ x_2,\\ x_3,\\ \\dots,\\ x_{n-1},\\ x_n]$$\n\nSplit it into half / half:\n$$[x_1,\\ x_2,\\ \\dots,\\ x_{n/2 - 2},\\ x_{n/2 - 1}]\\ \\ \\ \\mid\\ \\ \\ [x_{n/2},\\ x_{n/2 + 1},\\ \\dots,\\ x_n]$$\n\nLet call the left half `a` and right half `b`.\n\nIf we know the answer to both `a` and `b`, how can we use the answers to figure out the answer for the original array? Well, we can simply add up the answers to `a` and `b` because if we take the best from `a` and the best from `b`, we should get the best from `a + b`.\n\nRemember we have a constraint saying that the subsequence cannot contain adjacent elements in the original array.\n\nOkay, what about making a small tweak to the answers to `a` and `b`? Since we want to put both answers together to form a concatenated subsequence but we also need to avoid the concatenation brings in two adjacent elements, we can just use the **take-1-and-not-take-1 strategy**:\n$$[\\underline{x_1,\\ x_2,\\ \\dots,\\ x_{n/2 - 2},\\ x_{n/2 - 1}}]\\ \\ \\ \\mid\\ \\ \\ [x_{n/2},\\ \\underline{x_{n/2 + 1},\\ \\dots,\\ x_n}] \\leftarrow \\small\\text{take underlined numbers}$$\n$$[\\underline{x_1,\\ x_2,\\ \\dots,\\ x_{n/2 - 2}},\\ x_{n/2 - 1}]\\ \\ \\ \\mid\\ \\ \\ [\\underline{x_{n/2},\\ x_{n/2 + 1},\\ \\dots,\\ x_n}] \\leftarrow \\small\\text{take underlined numbers}$$\n\nIf we include the rightmost element in `a`, we cannot include the leftmost element in `b`. If we don\'t include the rightmost element in `a`, we can include the leftmost element in `b`.\n\nCool, so we now know the answer to the original array:\n```javascript\nanswer(a + b) = Math.max(\n    answerWithRight(a) + answerWithoutLeft(b),\n    answerWithoutRight(a) + answerWithLeft(b),\n)\n```\n\nWe have left and right, two dimensions, and therefore, four enumerations:\n1. With leftmost and rightmost elements\n2. With leftmost element but without rightmost element\n3. With rightmost element but without leftmost element\n4. Without leftmost and rightmost elements\n\n## Create A Segment Tree\nKeep in mind that segment tree is just a data structure. The code you put into a segment tree data structure is the same as you would put in a divide and conquer algorithm.\n\nGiven a tree node (i.e. the original problem), its value (i.e. answers to the four enumerations) can be calculated from its two child nodes:\n```javascript\nconst node = new SegmentTreeNode(a + b); // a + b denotes the original array\n\nnode.left = new SegmentTreeNode(a); // a is the left half\nnode.left.solve(); // divide and conquer to solve left half\n\nnode.right = new SegmentTreeNode(b); // b is the right half\nnode.right.solve(); // divide and conquer to solve right half\n\n// answers to the four enumrations\nnode.val = {\n    leftAndRight: Math.max(\n        node.left.val.leftNoRight + node.right.val.leftAndRight,\n        node.left.val.leftAndRight + node.right.val.rightNoLeft,\n    ),\n    leftNoRight: Math.max(\n        node.left.val.leftNoRight + node.right.val.leftNoRight,\n        node.left.val.leftAndRight + node.right.val.noLeftNoRight,\n    ),\n    rightNoLeft: Math.max(\n        node.left.val.noLeftNoRight + node.right.val.leftAndRight,\n        node.left.val.rightNoLeft + node.right.val.rightNoLeft,\n    ),\n    noLeftNoRight: Math.max(\n        node.left.val.noLeftNoRight + node.right.val.leftNoRight,\n        node.left.val.rightNoLeft + node.right.val.noLeftNoRight,\n    ),\n};\n```\n\nWhen we handle updates, we just need to recurse on the corresponding child node based on the index of the element in the array to be updated.\n```javascript\n// node.lb and node.rb denotes the left and right indices of the array in the sub-problem\nupdate(i, val) {\n    if (node.lb === node.rb) { // this is a leaf node\n        node.val = {...}; // update leaf node\'s answer\n        return;\n    }\n    if (i >= node.left.lb && i <= node.left.rb) {\n        node.left.update(i, val);\n    } else {\n        node.right.update(i, val);\n    }\n    node.solve(); // solve the problem after the corresponding child node is updated\n}\n```\n\n# Complexity\n- Time complexity: $O(\\log(n)\\cdot q)$ where $n$ is the length of `nums` and $q$ is the length of `queries`.\n\n- Space complexity: $O(n)$ where $n$ is the length of `nums` because space of a segment tree is at most $4n$.\n\n# Code\n```javascript []\nclass SegmentTreeNode {\n    static build(arr, l, r) {\n        const root = new SegmentTreeNode(l, r);\n        if (l === r) {\n            root.val = {\n                leftAndRight: arr[l],\n                leftNoRight: 0,\n                rightNoLeft: 0,\n                noLeftNoRight: 0,\n            };\n            return root;\n        }\n        const mid = Math.floor((l + r) / 2);\n        root.left = SegmentTreeNode.build(arr, l, mid);\n        root.right = SegmentTreeNode.build(arr, mid + 1, r);\n        root.merge();\n        return root;\n    }\n\n    constructor(lb, rb) {\n        this.lb = lb;\n        this.rb = rb;\n        this.val = {};\n        this.left = null;\n        this.right = null;\n    }\n\n    merge() {\n        const MOD = 1e9 + 7;\n        this.val = {\n            leftAndRight: Math.max(\n                this.left.val.leftNoRight + this.right.val.leftAndRight,\n                this.left.val.leftAndRight + this.right.val.rightNoLeft,\n            ) % MOD,\n            leftNoRight: Math.max(\n                this.left.val.leftNoRight + this.right.val.leftNoRight,\n                this.left.val.leftAndRight + this.right.val.noLeftNoRight,\n            ) % MOD,\n            rightNoLeft: Math.max(\n                this.left.val.noLeftNoRight + this.right.val.leftAndRight,\n                this.left.val.rightNoLeft + this.right.val.rightNoLeft,\n            ) % MOD,\n            noLeftNoRight: Math.max(\n                this.left.val.noLeftNoRight + this.right.val.leftNoRight,\n                this.left.val.rightNoLeft + this.right.val.noLeftNoRight,\n            ) % MOD,\n        };\n    }\n\n    update(i, val) {\n        if (this.lb === this.rb) {\n            this.val = {\n                leftAndRight: val,\n                leftNoRight: 0,\n                rightNoLeft: 0,\n                noLeftNoRight: 0,\n            };\n            return;\n        }\n        if (i >= this.left.lb && i <= this.left.rb) {\n            this.left.update(i, val);\n        } else {\n            this.right.update(i, val);\n        }\n        this.merge();\n    }\n}\n\n/**\n * @param {number[]} nums\n * @param {number[][]} queries\n * @return {number}\n */\nvar maximumSumSubsequence = function(nums, queries) {\n    const MOD = 1e9 + 7;\n    const segmentTree = SegmentTreeNode.build(nums, 0, nums.length - 1);\n    let result = 0;\n    for (const [i, val] of queries) {\n        segmentTree.update(i, val);\n        const max = Math.max(...Object.values(segmentTree.val));\n        result = (result + max) % MOD;\n    }\n    return result;\n};\n```
['Divide and Conquer', 'JavaScript']