2022-09-15：Range 模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为半开区间的范围并查询它们。半开区间 [left, right) 表示所有 left ＜= x ＜ righ

2022 年 9 月 15 日
北京
本文字数：2044 字
阅读完需：约 7 分钟

2022-09-15：Range 模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为半开区间的范围并查询它们。半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。实现 RangeModule 类:RangeModule() 初始化数据结构的对象 void addRange(int left, int right) :添加半开区间 [left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。boolean queryRange(int left, int right) :只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true 否则返回 false 。void removeRange(int left, int right) :停止跟踪半开区间 [left, right) 中当前正在跟踪的每个实数。输入：["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"][[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]。输出：[null, null, null, true, false, true]。

答案 2022-09-15：

这是力扣 715 的题。用有序表。动态开点线段树也行。这道题是 java 运行速度远远领先 go，但这是特例。其他力扣题，基本是持平的。内存上来说，java 是 go 的好几倍。综合来说，go 比 java 省资源。rust 自然是最省资源的，运行速度也是最快的。

代码用 rust 编写，代码如下：

use std::collections::BTreeMap;
struct RangeModule {    map: BTreeMap<i32, i32>,}
impl RangeModule {    fn new() -> Self {        Self {            map: BTreeMap::new(),        }    }
    fn add_range(&mut self, left: i32, right: i32) {        if right <= left {            return;        }        let start = self.map.range(..=left).last();        let mut start_key = 0;        let mut start_value = 0;        if !start.is_none() {            start_key = *start.unwrap().0;            start_value = *start.unwrap().1;        }
        let end = self.map.range(..=right).last();        let mut end_key = 0;        let mut end_value = 0;        if !end.is_none() {            end_key = *end.unwrap().0;            end_value = *end.unwrap().1;        }        if start.is_none() && end.is_none() {            self.map.insert(left, right);        } else if !start.is_none() && start_value >= left {            self.map.insert(start_key, get_max(end_value, right));        } else {            self.map.insert(left, get_max(end_value, right));        }        let mut sets: Vec<i32> = vec![];        for (k, _) in self.map.range(left+1..=right) {            sets.push(*k);        }        for s in sets.iter() {            self.map.remove(s);        }    }
    fn query_range(&mut self, left: i32, right: i32) -> bool {        let start = self.map.range(..=left).last();        let mut start_key = 0;        let mut start_value = 0;        if !start.is_none() {            start_key = *start.unwrap().0;            start_value = *start.unwrap().1;        }        if start.is_none() {            return false;        }        return start_value >= right;    }
    fn remove_range(&mut self, left: i32, right: i32) {        if right <= left {            return;        }        let start = self.map.range(..=left).last();        let mut start_key = 0;        let mut start_value = 0;        let mut start_is_none = true;        if !start.is_none() {            start_key = *start.unwrap().0;            start_value = *start.unwrap().1;            start_is_none = false;        }
        let end = self.map.range(..=right).last();        let mut end_key = 0;        let mut end_value = 0;        let mut end_is_none = true;        if !end.is_none() {            end_key = *end.unwrap().0;            end_value = *end.unwrap().1;            end_is_none = false;        }        if !end_is_none && end_value > right {            self.map.insert(right, end_value);        }        if !start_is_none && start_value > left {            self.map.insert(start_key, left);        }
        let mut sets: Vec<i32> = vec![];        for (k, _) in self.map.range(left..right) {            sets.push(*k);        }        for s in sets.iter() {            self.map.remove(s);        }    }}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a > b {        a    } else {        b    }}