[Readability][C++][Segment Tree] Clean and reusable implementation
Complexity\n\n- Time complexity: $O(q\log n)$\n- Space complexity: $O(n)$\n\n# Code\n\ncpp\ntemplate <typename NodeType, typename ValueType>\nclass RangeQuery {
# Complexity\n\n- Time complexity: $O(q\\log n)$\n- Space complexity: $O(n)$\n\n# Code\n\n```cpp\ntemplate <typename NodeType, typename ValueType>\nclass RangeQuery {\n public:\n  virtual void update(int index, ValueType val);\n  virtual NodeType query(int i, int j);\n\n private:\n  // Merges the result of the left node and the right node.\n  virtual NodeType merge(const NodeType& a, const NodeType& b);\n\n protected:\n  int left(int treeIndex) {\n    return 2 * treeIndex + 1;\n  }\n\n  int right(int treeIndex) {\n    return 2 * treeIndex + 2;\n  }\n};\n\nclass SegmentTree : RangeQuery<vector<vector<int>>, int> {\n public:\n  explicit SegmentTree(const vector<int>& nums, int n, int kInf)\n      : n(n), kInf(kInf), tree(4 * n, vector<vector<int>>(2, vector<int>(2))) {\n    build(nums, 0, 0, n - 1);\n  }\n\n  // Updates nums[i] to val equivalently.\n  void update(int i, int val) override {\n    update(0, 0, n - 1, i, val);\n  }\n\n  // Returns sum(nums[i..j]).\n  vector<vector<int>> query(int i, int j) override {\n    return query(0, 0, n - 1, i, j);\n  }\n\n private:\n  const int n;     // the size of the input array\n  const int kInf;  // the invalid value\n  // tree[i][l][r] := the value of the i-th node, where `l` and `r` represent if\n  // the leftmost or rightmost element is selected, respectively\n  vector<vector<vector<int>>> tree;\n\n  void build(const vector<int>& nums, int treeIndex, int lo, int hi) {\n    if (lo == hi) {\n      tree[treeIndex][0][0] = 0;\n      tree[treeIndex][0][1] = -kInf;\n      tree[treeIndex][1][0] = -kInf;\n      tree[treeIndex][1][1] = nums[lo];\n      return;\n    }\n    const int mid = (lo + hi) / 2;\n    const int leftTreeIndex = left(treeIndex);\n    const int rightTreeIndex = right(treeIndex);\n    build(nums, leftTreeIndex, lo, mid);\n    build(nums, rightTreeIndex, mid + 1, hi);\n    tree[treeIndex] = merge(tree[leftTreeIndex], tree[rightTreeIndex]);\n  }\n\n  void update(int treeIndex, int lo, int hi, int i, int val) {\n    if (lo == hi) {\n      tree[treeIndex][0][0] = 0;\n      tree[treeIndex][1][1] = val;\n      return;\n    }\n    const int mid = (lo + hi) / 2;\n    const int leftTreeIndex = left(treeIndex);\n    const int rightTreeIndex = right(treeIndex);\n    if (i <= mid)\n      update(leftTreeIndex, lo, mid, i, val);\n    else\n      update(rightTreeIndex, mid + 1, hi, i, val);\n    tree[treeIndex] = merge(tree[leftTreeIndex], tree[rightTreeIndex]);\n  }\n\n  vector<vector<int>> query(int treeIndex, int lo, int hi, int i, int j) {\n    // [lo, hi] lies completely inside [i, j].\n    if (i <= lo && hi <= j)\n      return tree[treeIndex];\n    // [lo, hi] lies completely outside [i, j].\n    if (j < lo || hi < i)\n      return vector<vector<int>>{{-kInf, -kInf}, {-kInf, -kInf}};\n    const int mid = (lo + hi) / 2;\n    return merge(query(left(treeIndex), lo, mid, i, j),\n                 query(right(treeIndex), mid + 1, hi, i, j));\n  }\n\n  vector<vector<int>> merge(const vector<vector<int>>& a,\n                            const vector<vector<int>>& b) override {\n    vector<vector<int>> node(2, vector<int>(2));\n    for (int l = 0; l < 2; ++l)\n      for (int r = 0; r < 2; ++r)\n        node[l][r] =\n            max({a[l][0] + b[0][r], a[l][0] + b[1][r], a[l][1] + b[0][r]});\n    return node;\n  }\n};\n\nclass Solution {\n public:\n  int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n    constexpr int kMod = 1\'000\'000\'007;\n    constexpr int kInf = 1\'000\'000\'000;\n    const int n = nums.size();\n    int ans = 0;\n    SegmentTree tree(nums, n, kInf);\n\n    for (const vector<int>& query : queries) {\n      const int pos = query[0];\n      const int x = query[1];\n      tree.update(pos, x);\n      vector<vector<int>> res = tree.query(0, n - 1);\n      ans = (ans + max({res[0][0], res[0][1], res[1][0], res[1][1]})) % kMod;\n    }\n\n    return ans;\n  }\n};\n```
['C++']