JS solution - Segment tree
Pro tip: Love Xie Chu Ling \uD83D\uDC9C\n\n# Complexity\n- Let n = nums.length\n- Time complexity: O(nlogn)\n- Space complexity: O(n)\n\n# Code\njs\nlet MAX = 5
Pro tip: Love Xie Chu Ling \uD83D\uDC9C\n\n# Complexity\n- Let `n = nums.length`\n- Time complexity: $$O(nlogn)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```js\nlet MAX = 5e4;\nlet MOD = 1000000007;\nlet NOO = -1e9;\n\n/** @type {number[][]} */\nlet dp = Array.from({ length: 4 * (MAX + 1) }, () => Array(4).fill(0));\n\nfunction pushUp(node) {\n  dp[node].fill(0);\n  let c = node << 1;\n\n  for (let ls = 0; ls < 4; ls++) {\n    for (let rs = 0; rs < 4; rs++) {\n      let s = (ls & 2) | (rs & 1);\n\n      if ((ls & 1) && (rs & 2)) {\n        continue;\n      }\n\n      dp[node][s] = Math.max(dp[node][s], dp[c + 1][ls] + dp[c + 2][rs]);\n    }\n  }\n}\n\nfunction build(nums, node, l, r) {\n  if (l == r) {\n    dp[node][0] = 0;\n    dp[node][1] = NOO;\n    dp[node][2] = NOO;\n    dp[node][3] = nums[l];\n\n    return;\n  }\n\n  let m = (l + r) >> 1;\n  let c = node << 1;\n\n  build(nums, c + 1, l, m);\n  build(nums, c + 2, m + 1, r);\n  pushUp(node);\n}\n\nfunction set(qi, qv, node, l, r) {\n  if (l == r) {\n    dp[node][0] = 0;\n    dp[node][1] = NOO;\n    dp[node][2] = NOO;\n    dp[node][3] = qv;\n\n    return;\n  }\n\n  let m = (l + r) >> 1;\n  let c = node << 1;\n\n  if (qi <= m) {\n    set(qi, qv, c + 1, l, m);\n  } else {\n    set(qi, qv, c + 2, m + 1, r);\n  }\n\n  pushUp(node);\n}\n\n/**\n * @param {number[]} nums\n * @param {number[][]} queries\n * @return {number}\n */\nvar maximumSumSubsequence = function (nums, queries) {\n  let n = nums.length;\n  let m = queries.length;\n  let res = 0;\n\n  build(nums, 0, 0, n - 1);\n\n  for (let i = 0; i < m; i++) {\n    let [pos, val] = queries[i];\n    set(pos, val, 0, 0, n - 1)\n\n    let cur = Math.max(dp[0][0], dp[0][1], dp[0][2], dp[0][3]);\n    res = (res + cur) % MOD;\n  }\n\n  return res;\n};\n```
['Dynamic Programming', 'Segment Tree', 'JavaScript']