[C++] [Segment Tree] [O(n logn)] Beats 100.00%💯💯 10 min to understand 🔥🔥
Intuition\nUse Segment Tree, each node stores 4 values (front and back back not selected, front selected, back selected, both front and back elements selected) 
# Intuition\nUse Segment Tree, each node stores 4 values (front and back back not selected, front selected, back selected, both front and back elements selected) from merged arrays of two child node.\n\n`dp[node_index][0]` neither front nor back are selected\n`dp[node_index][1]` front element selected\n`dp[node_index][2]` back element selected\n`dp[node_index][3]` both front and back elements are selected.\n\nFor example: left child: `1 2 3 4`, right child: `5 6 7 8`.\nFather Node with `dp[node_index][0]`: `2 3 4 5 6 7`\nFather Node with `dp[node_index][1]`: ` 1 2 3 4 5 6 7`\n\nWhen node merged from its left and right child, there are 3 cases of selection of back element of l child and front element of r child \n\n# Approach\nConstruct the ST.\nUpdate the ST\n\n# Complexity\n- Time complexity:\n    O(n log n)\n\n- Space complexity:\n    O(n)\n\n# Code\n```\nvoid\nbuildST(int node_index, int l, int r, vector<vector<int>> &dp, vector<int> &nums) {\n    if (l == r) {\n        dp[node_index][0] = 0;\n        dp[node_index][1] = 0;\n        dp[node_index][2] = 0;\n        dp[node_index][3] = nums[l];\n    } else {\n        int mid = (l + r) / 2;\n        buildST(2 * node_index, l, mid, dp, nums);\n        buildST(2 * node_index + 1, mid + 1, r, dp, nums);\n        if (l == r) {\n            dp[node_index][0] = 0;                         // 0 0\n            dp[node_index][1] = dp[2 * node_index][1];     // 1 0\n            dp[node_index][2] = dp[2 * node_index + 1][1]; // 0 1\n            dp[node_index][3] = dp[2 * node_index + 1][1]; // 11\n        } else {\n            dp[node_index][0] = max(dp[2 * node_index][0] + dp[2 * node_index + 1][0],\n                                    max(dp[2 * node_index][2] + dp[2 * node_index + 1][0],\n                                        dp[2 * node_index][0] + dp[2 * node_index + 1][1]));\n            dp[node_index][1] = max(dp[2 * node_index][1] + dp[2 * node_index + 1][0],\n                                    max(dp[2 * node_index][1] + dp[2 * node_index + 1][1],\n                                        dp[2 * node_index][3] + dp[2 * node_index + 1][0]));\n            dp[node_index][2] = max(dp[2 * node_index][0] + dp[2 * node_index + 1][2],\n                                    max(dp[2 * node_index][2] + dp[2 * node_index + 1][2],\n                                        dp[2 * node_index][0] + dp[2 * node_index + 1][3]));\n            dp[node_index][3] = max(dp[2 * node_index][1] + dp[2 * node_index + 1][2],\n                                    max(dp[2 * node_index][1] + dp[2 * node_index + 1][3],\n                                        dp[2 * node_index][3] + dp[2 * node_index + 1][2]));\n        }\n    }\n}\n\nvoid\nupdateST(int node_index, int l, int r, int idx, int val, vector<vector<int>> &dp) {\n\n    if (l == r) {\n        dp[node_index][0] = 0;\n        dp[node_index][1] = 0;\n        dp[node_index][2] = 0;\n        dp[node_index][3] = val;\n    } else {\n\n        int mid = (l + r) / 2;\n\n        if (l <= idx and idx <= mid)\n            updateST(2 * node_index, l, mid, idx, val, dp);\n        else\n            updateST(2 * node_index + 1, mid + 1, r, idx, val, dp);\n\n        dp[node_index][0] = max(dp[2 * node_index][0] + dp[2 * node_index + 1][0],\n                                max(dp[2 * node_index][2] + dp[2 * node_index + 1][0],\n                                    dp[2 * node_index][0] + dp[2 * node_index + 1][1]));\n        dp[node_index][1] = max(dp[2 * node_index][1] + dp[2 * node_index + 1][0],\n                                max(dp[2 * node_index][1] + dp[2 * node_index + 1][1],\n                                    dp[2 * node_index][3] + dp[2 * node_index + 1][0]));\n        dp[node_index][2] = max(dp[2 * node_index][0] + dp[2 * node_index + 1][2],\n                                max(dp[2 * node_index][2] + dp[2 * node_index + 1][2],\n                                    dp[2 * node_index][0] + dp[2 * node_index + 1][3]));\n        dp[node_index][3] = max(dp[2 * node_index][1] + dp[2 * node_index + 1][2],\n                                max(dp[2 * node_index][1] + dp[2 * node_index + 1][3],\n                                    dp[2 * node_index][3] + dp[2 * node_index + 1][2]));\n    }\n}\n\nclass Solution {\n  public:\n    int\n    maximumSumSubsequence(vector<int> &nums, vector<vector<int>> &queries) {\n        int                 n      = nums.size();\n        int                 q      = queries.size();\n        int                 result = 0;\n        vector<vector<int>> dp(4 * n, vector<int>(4));\n        for (int t = 0; t < q; t++) {\n            nums[queries[t][0]] = queries[t][1];\n\n            int left  = 0;\n            int right = nums.size() - 1;\n            int n     = nums.size();\n            if (t == 0) {\n                buildST(1, left, right, dp, nums);\n            } else {\n                updateST(1, left, right, queries[t][0], queries[t][1], dp);\n            }\n            int max_v = 0;\n            for (int i = 0; i < 4; i++) {\n                max_v = max(dp[1][i], max_v)% (1000000000 + 7);\n            }\n            result = (result + max_v) % (1000000000 + 7);\n        }\n        return result;\n    }\n};\n```\n\n# Questions? \n![woquyuepi.jpg](https://assets.leetcode.com/users/images/c8f85ada-410f-40be-9b0e-c3f90a6bb80c_1716844670.7167902.jpeg)\n
['C++']