My Solution
\n/**\n * Time Complexity: O(n_queries * log(n))\n * Space Complexity: O(n)\n * where `n` is the length of the vector `nums`\n *       `n_queries` is the length
```\n/**\n * Time Complexity: O(n_queries * log(n))\n * Space Complexity: O(n)\n * where `n` is the length of the vector `nums`\n *       `n_queries` is the length of the vector `queries`\n */\nclass Solution {\n private:\n  static constexpr int mod = 1000000007;\n  \n  class SegmentTree {\n   public:\n    SegmentTree(const vector<int> &nums)\n    : n_(static_cast<int>(nums.size()))\n    , nums_(nums)\n    , tree0_(tree_size())\n    , tree1_(tree0_.size())\n    , tree2_(tree1_.size())\n    , tree3_(tree2_.size()) {\n      build();\n    }\n    \n    void update(const int index, const int value) {\n      const int real_value = max(0, value);\n      if (nums_[index] == real_value) {\n        return;\n      }\n\n      nums_[index] = real_value;\n      update_impl(0, 0, n_, index, real_value);\n    }\n    \n    int query() const {\n      return tree3_.front();\n    }\n    \n   private:\n    int tree_size() const {\n      return (1 << (static_cast<int>(ceil(log2(n_))) + 1)) - 1;\n    }\n    \n    void build() {\n      build_impl(0, 0, n_);\n    }\n    \n    void build_impl(const int node, const int begin, const int end) {\n      if (end - begin <= 1) {\n        if (end - begin == 1 && nums_[begin] > 0) {\n          maintain_one(node, nums_[begin]);\n        }\n        return;\n      }\n      \n      const int left_node = (node << 1) + 1;\n      const int right_node = (node << 1) + 2;\n      const int mid = begin + ((end - begin) >> 1);\n      \n      build_impl(left_node, begin, mid);\n      build_impl(right_node, mid, end);\n      maintain(node, left_node, right_node);\n    }\n    \n    void update_impl(const int node, const int begin, const int end, const int index, const int value) {\n      if (index < begin || index >= end) {\n        return;\n      }\n      \n      if (end - begin == 1) {\n        maintain_one(node, value);\n        return;\n      }\n      \n      const int left_node = (node << 1) + 1;\n      const int right_node = (node << 1) + 2;\n      const int mid = begin + ((end - begin) >> 1);\n\n      update_impl(left_node, begin, mid, index, value);\n      update_impl(right_node, mid, end, index, value);\n      maintain(node, left_node, right_node);\n    }\n    \n    void maintain_one(const int node, const int value) {\n      tree0_[node] = 0;\n      tree1_[node] = 0;\n      tree2_[node] = 0;\n      tree3_[node] = value;\n    }\n    \n    void maintain(const int node, const int left_node, const int right_node) {\n      /**\n       * let `t00` be equal to tree0_\n       * let `t01` be equal to tree1_\n       * let `t10` be equal to tree2_\n       * let `t11` be equal to tree3_\n       * let `n` be `node`\n       * let `l` be `left_node`\n       * let `r` be `right_node`\n       *\n       * 00 => 00|10 or 01|00\n       * t00[n] = max(t00[l] + t10[r], t01[l] + t00[r])\n       */\n      tree0_[node] = max(tree0_[left_node] + tree2_[right_node], tree1_[left_node] + tree0_[right_node]) % mod;\n      /**\n       * 01 => 00|11 or 01|01\n       * t01[n] = max(t00[l] + t11[r], t01[l] + t01[r])\n       */\n      tree1_[node] = max(tree0_[left_node] + tree3_[right_node], tree1_[left_node] + tree1_[right_node]) % mod;\n      /**\n       * 10 => 10|10 or 11|00\n       * t10[n] = max(t10[l] + t10[r], t11[l] + t00[r])\n       */\n      tree2_[node] = max(tree2_[left_node] + tree2_[right_node], tree3_[left_node] + tree0_[right_node]) % mod;\n      /**\n       * 11 => 10|11 or 11|01\n       * t11[n] = max(t10[l] + t11[r], t11[l] + t01[r])\n       */\n      tree3_[node] = max(tree2_[left_node] + tree3_[right_node], tree3_[left_node] + tree1_[right_node]) % mod;\n    }\n    \n    const int n_;\n    vector<int> nums_;\n    /**\n     * tree0_[node] is the maximum sum of a subsequence of\n     *                 the sub-vector `sv` represented by `node` where\n     *                 1. no two adjacent elements are selected and\n     *                 2. the first element and the last element of the sub-vector `sv` is not selected\n     */\n    vector<int> tree0_;\n    /**\n     * tree1_[node] is the maximum sum of a subsequence of\n     *                 the sub-vector `sv` represented by `node` where\n     *                 1. no two adjacent elements are selected and\n     *                 2. the first element of the sub-vector `sv` is not selected and\n     *                 3. the last element of the sub-vector `sv` can be selected or unselected\n     */\n    vector<int> tree1_;\n    /**\n     * tree2_[node] is the maximum sum of a subsequence of\n     *                 the sub-vector `sv` represented by `node` where\n     *                 1. no two adjacent elements are selected and\n     *                 2. the first element of the sub-vector `sv` can be selected or unselected and\n     *                 3. the last element of the sub-vector `sv` is not selected\n     */   \n    vector<int> tree2_;\n    /**\n     * tree3_[node] is the maximum sum of a subsequence of\n     *                 the sub-vector `sv` represented by `node` where\n     *                 1. no two adjacent elements are selected and\n     *                 2. the first element of the sub-vector `sv` can be selected or unselected and\n     *                 3. the last element of the sub-vector `sv` can be selected or unselected\n     */   \n    vector<int> tree3_;\n  };\n  \n public:\n  int maximumSumSubsequence(const vector<int> &nums, const vector<vector<int>> &queries) {\n    const int n = static_cast<int>(nums.size());\n    SegmentTree segment_tree(nums);\n    int ret = 0;\n    for (const vector<int> &query : queries) {\n      const int index = query.front();\n      const int value = query.back();\n      segment_tree.update(index, value);\n      ret = (ret + segment_tree.query()) % mod;\n    }\n    return ret;\n  }\n};\n```
[]