Rust/Python Segment tree with detailed explanation
Intuition\n\nWhen you have a lot of updates and queries of the array, it might make sense to look at a segment tree. An excellent explanation where I learnt abo
# Intuition\n\nWhen you have a lot of updates and queries of the array, it might make sense to look at a segment tree. An excellent explanation where I learnt about it is https://cp-algorithms.com/data_structures/segment_tree.html\n\nIt explains everythings:\n- how to build a tree\n- how to do updates \n- why we have 4 * n nodes, and why do you have this specific complexity\n\nNow you do not need range. The results will be in tree[1] after each update. The most important questions about segment tree are:\n\n - what to store in a node\n - how to merge elements\n\nIf you have two sequences and you need to merge them, there are 4 options (based on first and last element included or excluded). So lets have:\n\n1. A: included, included\n2. B: included, excluded\n3. C: excluded, included\n4. D: excluded, excluded\n\nNow how can you merge those two elements to get each element you need to try a few approaches and select the biggest one. \n\n- A: A1 + C2, B1 + A2, B1 + C2\n- B: A1 + D2, B1 + B2, B1 + D2\n- C: C1 + C2, D1 + A2, D1 + C2\n- D: C1 + D2, D1 + B2, D1 + D2\n\nSo in each node you need to store 4 elements. And in merge you have 3 operations and maximum of them to get combined node.\n\n\n# Complexity\n- Time complexity: $O(n)$ to build a tree, and $O(\\log n)$ for each query\n- Space complexity: $O(n)$\n\n# Code\n```Rust []\nstruct SegmentTree {\n  n: usize,\n  tree: Vec<[i32; 4]>,\n}\n\n\nimpl SegmentTree {\n\n  fn new(arr: Vec<i32>) -> Self {\n    let mut tree = SegmentTree {\n      n: arr.len(),\n      tree: vec![[0; 4]; 4 * arr.len()],\n    };\n    tree.build(&arr, 1, 0, arr.len() - 1);\n    return tree;\n  }\n\n  fn build(&mut self, arr: &Vec<i32>, pos: usize, l: usize, r: usize) {\n    if l == r {\n      self.tree[pos][0] = arr[l].max(0);\n    } else {\n      let m = (l + r) / 2;\n      self.build(arr, 2 * pos, l, m);\n      self.build(arr, 2 * pos + 1, m + 1, r);\n      \n      let v1 = self.tree[2 * pos];\n      let v2 = self.tree[2 * pos + 1];\n      self.tree[pos] = [\n        (v1[0] + v2[2]).max(v1[1] + v2[0]).max(v1[1] + v2[2]),\n        (v1[0] + v2[3]).max(v1[1] + v2[1]).max(v1[1] + v2[3]),\n        (v1[2] + v2[2]).max(v1[3] + v2[0]).max(v1[3] + v2[2]),\n        (v1[2] + v2[3]).max(v1[3] + v2[1]).max(v1[3] + v2[3]),\n      ];\n    }\n  }\n\n  fn _update(&mut self, ind: usize, val: i32, pos: usize, l: usize, r: usize) {\n    if l == r {\n      self.tree[pos][0] = val.max(0);\n    } else {\n      let m = (l + r) / 2;\n      if ind <= m {\n        self._update(ind, val, 2 * pos, l, m);\n      } else {\n        self._update(ind, val, 2 * pos + 1, m + 1, r);\n      }\n      \n      let v1 = self.tree[2 * pos];\n      let v2 = self.tree[2 * pos + 1];\n      self.tree[pos] = [\n        (v1[0] + v2[2]).max(v1[1] + v2[0]).max(v1[1] + v2[2]),\n        (v1[0] + v2[3]).max(v1[1] + v2[1]).max(v1[1] + v2[3]),\n        (v1[2] + v2[2]).max(v1[3] + v2[0]).max(v1[3] + v2[2]),\n        (v1[2] + v2[3]).max(v1[3] + v2[1]).max(v1[3] + v2[3]),\n      ];\n    }\n  }\n\n  fn update(&mut self, ind: usize , val: i32) {\n    self._update(ind, val, 1, 0, self.n - 1);\n  }\n}\n\n\nimpl Solution {\n  pub fn maximum_sum_subsequence(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {\n    let mut st = SegmentTree::new(nums);\n    let mut res = 0;\n    for v in queries {\n      st.update(v[0] as usize, v[1]);\n      res = (res + st.tree[1][0].max(st.tree[1][1]).max(st.tree[1][2]).max(st.tree[1][3])) % 1000000007;\n    }\n\n    return res;\n  }\n}\n```\n```python []\nclass SegmentTree:\n\n  def __init__(self, arr: List[int]):\n    self.n = len(arr)\n    self.tree = [[0, 0, 0, 0] for _ in range(4 * self.n)]\n    self._build(arr, 1, 0, self.n - 1)\n\n  def _merge(self, v1: List[int], v2: List[int]) -> List[int]:\n    a1, b1, c1, d1 = v1\n    a2, b2, c2, d2 = v2\n\n    return [\n      max(a1 + c2, b1 + a2, b1 + c2),\n      max(a1 + d2, b1 + b2, b1 + d2),\n      max(c1 + c2, d1 + a2, d1 + c2),\n      max(c1 + d2, d1 + b2, d1 + d2),\n    ]\n\n  def _build(self, arr: List[int], pos: int, l: int, r: int):\n    if l == r:\n      self.tree[pos][0] = max(0, arr[l])\n    else:\n      m = (l + r) // 2\n      self._build(arr, 2 * pos, l, m)\n      self._build(arr, 2 * pos + 1, m + 1, r)\n      self.tree[pos] = self._merge(self.tree[2 * pos], self.tree[2 * pos + 1])\n\n  def _update(self, ind: int, new_val: int, pos: int, l: int, r: int):\n    if l == r:\n      self.tree[pos][0] = max(0, new_val)\n    else:\n      m = (l + r) // 2\n      if ind <= m:\n        self._update(ind, new_val, 2 * pos, l, m)\n      else:\n        self._update(ind, new_val, 2 * pos + 1, m + 1, r)\n      self.tree[pos] = self._merge(self.tree[2 * pos], self.tree[2 * pos + 1])\n\n  def update(self, ind: int, new_val: int):\n    self._update(ind, new_val, 1, 0, self.n - 1)\n  \n\nclass Solution:\n  def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:\n    st, res = SegmentTree(nums), 0\n    for ind, new_val in queries:\n      st.update(ind, new_val)\n      res = (res + max(st.tree[1])) % (10**9 + 7)\n    \n    return res\n```\n
['Python3', 'Rust']