An entry-level Rust solution
Intuition\n Describe your first thoughts on how to solve this problem. \n- First try: DP -> TLE @ 517\n- Second try: Segment tree, each node stores 4 sum result
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- First try: DP -> TLE @ 517\n- Second try: Segment tree, each node stores 4 sum results as given in Hint 2.\n\n\n# Code\n```\nuse std::cmp::max;\n\n/// A segment tree node to store the maximum sequence sum with no adjacent (MSSNA).\nstruct TreeNode {\n    /// The range of the current node\n    range: (usize, usize),\n    /// The left child node\n    left: Option<Box<TreeNode>>,\n    /// The right child node\n    right: Option<Box<TreeNode>>,\n    /// Store different MSSNA values\n    /// `max_sums[0]`: MSSNA including both left and right range ends\n    /// `max_sums[1]`: MSSNA including only left range end\n    /// `max_sums[2]`: MSSNA including only right range end\n    /// `max_sums[3]`: MSSNA excluding both left and right range ends\n    max_sums: Vec<i32>,\n}\n\nimpl TreeNode {\n    /// Recursively construct the segment tree and return the root node\n    pub fn construct(nums: &Vec<i32>, left: usize, right: usize) -> TreeNode {\n        // reach the leaf node\n        if left == right {\n            return TreeNode {\n                range: (left, right),\n                left: None,\n                right: None,\n                max_sums: vec![max(0, nums[left]), 0, 0, 0],\n            };\n        }\n        let mid = (left + right) / 2;\n        let left_node = TreeNode::construct(nums, left, mid);\n        let right_node = TreeNode::construct(nums, mid + 1, right);\n\n        TreeNode {\n            max_sums: compute_max_sums(&left_node, &right_node),\n            range: (left, right),\n            left: Some(Box::new(left_node)),\n            right: Some(Box::new(right_node)),\n        }\n    }\n\n    /// Returns the maximum subsequence sum of the current node\n    pub fn query(&self) -> i32 {\n        max(\n            max(self.max_sums[0], self.max_sums[1]),\n            max(self.max_sums[2], self.max_sums[3]),\n        )\n    }\n\n    /// Recursively the value of the `idx`-th element in the array\n    pub fn update(&mut self, idx: usize, val: i32) {\n        // the `idx` child node is not a descendant of the current node\n        if self.range.0 > idx || self.range.1 < idx {\n            return;\n        }\n        // base case: reach the leaf node\n        if self.range.0 == self.range.1 && self.range.0 == idx {\n            self.max_sums = vec![max(0, val), 0, 0, 0];\n            return;\n        }\n        // update the left or right child node\n        let mid = (self.range.0 + self.range.1) / 2;\n        if idx <= mid {\n            // update the left child node\n            self.left.as_mut().unwrap().update(idx, val);\n        } else {\n            // update the right child node\n            self.right.as_mut().unwrap().update(idx, val);\n        }\n        // update the current node\n        self.max_sums =\n            compute_max_sums(&self.left.as_ref().unwrap(), &self.right.as_ref().unwrap());\n    }\n}\n\n/// Compute `max_sums` of the current node\nfn compute_max_sums(left: &TreeNode, right: &TreeNode) -> Vec<i32> {\n    // to calculate the `max_sums[0]` of the current node,\n    // there are three cases:\n    // 1. [] + (]  (`left.max_sums[0] + right.max_sums[2]`)\n    // 2. [) + (]  (`left.max_sums[1] + right.max_sums[2]`)\n    // 3. [) + []  (`left.max_sums[1] + right.max_sums[0]`)\n    let case_0 = left.max_sums[0] + right.max_sums[2];\n    let case_1 = left.max_sums[1] + right.max_sums[2];\n    let case_2 = left.max_sums[1] + right.max_sums[0];\n    let max_sum_0 = max(max(case_0, case_1), case_2);\n\n    // to calculate the `max_sums[1]` of the current node,\n    // there are three cases:\n    // 1. [] + ()  (`left.max_sums[0] + right.max_sums[3]`)\n    // 2. [) + ()  (`left.max_sums[1] + right.max_sums[3]`)\n    // 3. [) + [)  (`left.max_sums[1] + right.max_sums[1]`)\n    let case_0 = left.max_sums[0] + right.max_sums[3];\n    let case_1 = left.max_sums[1] + right.max_sums[3];\n    let case_2 = left.max_sums[1] + right.max_sums[1];\n    let max_sum_1 = max(max(case_0, case_1), case_2);\n\n    // to calculate the `max_sums[2]` of the current node,\n    // there are three cases:\n    // 1. () + []  (`left.max_sums[3] + right.max_sums[0]`)\n    // 2. () + (]  (`left.max_sums[3] + right.max_sums[2]`)\n    // 3. (] + (]  (`left.max_sums[2] + right.max_sums[2]`)\n    let case_0 = left.max_sums[3] + right.max_sums[0];\n    let case_1 = left.max_sums[3] + right.max_sums[2];\n    let case_2 = left.max_sums[2] + right.max_sums[2];\n    let max_sum_2 = max(max(case_0, case_1), case_2);\n\n    // to calculate the `max_sums[3]` of the current node,\n    // there are three cases:\n    // 1. () + ()  (`left.max_sums[3] + right.max_sums[3]`)\n    // 2. () + [)  (`left.max_sums[3] + right.max_sums[1]`)\n    // 3. (] + ()  (`left.max_sums[2] + right.max_sums[3]`)\n    let case_0 = left.max_sums[3] + right.max_sums[3];\n    let case_1 = left.max_sums[3] + right.max_sums[1];\n    let case_2 = left.max_sums[2] + right.max_sums[3];\n    let max_sum_3 = max(max(case_0, case_1), case_2);\n\n    vec![max_sum_0, max_sum_1, max_sum_2, max_sum_3]\n}\n\n/// Update the segment tree for each query and\n/// sum up the maximum subsequence sum of each range\nfn solution(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {\n    let mut res = 0;\n    let mut root = TreeNode::construct(&nums, 0, nums.len() - 1);\n    for query in queries {\n        root.update(query[0] as usize, query[1]);\n        res += root.query();\n        res %= 1_000_000_007;\n    }\n    res\n}\n\n```
['Rust']