Rust Segment Tree
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N * Log N)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N)\n# Code\n```\nuse std::collections::BTreeSet;\n\nimpl Solution {\n    pub fn maximum_sum_queries(nums1: Vec<i32>, nums2: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {\n        let mut s = BTreeSet::new();\n        for a in &nums2 { s.insert(*a); }\n\n        let data = s.into_iter().collect::<Vec<i32>>();\n        let (m, n, sz) = (nums1.len(), queries.len(), data.len()); \n        let mut tree = vec![(-1, -1); 4 * sz];\n        let (mut nums, mut temp) = (vec![], vec![]);\n        \n        for i in 0 .. m { nums.push((nums1[i], nums2[i])); }\n        for i in 0 .. n { temp.push((queries[i][0], queries[i][1], i)); }\n        nums.sort();\n        temp.sort();\n    \n        let mut k = m;\n        let mut ret = vec![-1; n];\n        while let Some(q) = temp.pop() {\n            while k > 0  && nums[k - 1].0 >= q.0 {\n                k -= 1;\n                let (a, b) = (nums[k].0, nums[k].1);\n                let idx = Self::binary_search(&data, b);\n                Self::update(1, 0, sz - 1, idx, a + b, &mut tree); \n            }\n            let j = Self::binary_search(&data, q.1);\n            ret[q.2] = Self::get(1, 0, sz - 1, j, &mut tree);\n        }\n\n        ret\n    }\n\n    fn update(u: usize, l: usize, r: usize, i: usize, a: i32, tree: &mut Vec<(i32, i32)>) {\n        if l > i { return }\n        if r <= i {\n            tree[u].0 = tree[u].0.max(a);\n            tree[u].1 = tree[u].1.max(tree[u].0);\n            return;\n        }\n\n        let m = l + (r - l) / 2;\n        Self::update(2 * u, l, m, i, a, tree);\n        Self::update(2 * u + 1, m + 1, r, i, a, tree);\n        let t = tree[2 * u].1.max(tree[2 * u + 1].1);\n        tree[u].1 = tree[u].1.max(t);\n    }\n\n    fn get(u: usize, l: usize, r: usize, i: usize, tree: &mut Vec<(i32, i32)>) -> i32 {\n        if i > r { return -1 }\n        if (l >= i) { return tree[u].0.max(tree[u].1); }\n\n        if tree[u].0 != -1 {\n            tree[u].1 = tree[u].1.max(tree[u].0);\n            if l < r {\n                tree[2 * u].0 = tree[2 * u].0.max(tree[u].0);\n                tree[2 * u + 1].0 = tree[2 * u + 1].0.max(tree[u].0); \n            }\n            tree[u].0 = -1;\n        }\n\n        let m = l + (r - l) / 2;\n        let (ret1, ret2) = (Self::get(2 * u, l, m, i, tree), Self::get(2 * u + 1, m + 1, r, i, tree));\n        let t = tree[2 * u].1.max(tree[2 * u + 1].1);\n        tree[u].1 = tree[u].1.max(t);\n\n        ret1.max(ret2)\n    }\n\n    fn binary_search(data: &Vec<i32>, a: i32) -> usize {\n        let (mut l, mut r) = (0, data.len() - 1);\n        if a > data[r] { return r + 1 }\n\n        while l < r {\n            let m = l + (r - l) / 2;\n            if data[m] < a { l = m + 1; }\n            else           { r = m; } \n        }\n\n        l\n    }\n}\n```
['Rust']