# 0715. Range Module
###### tags: `Leetcode` `Hard` `TreeMap`
Link: https://leetcode.com/problems/range-module/description/
## 思路
不能用差分法做 因为这样每一次```addRange```和```removeRange```都要重新扫一遍所有的key
思路参考[这里](https://leetcode.com/problems/range-module/solutions/947942/java-treemap-concise-code-adding-before-removing-simplify-the-code/)
我们把map的key当作interval的left, value当作interval的right
遇到```addRange()``` 我们把新的interval和已有的合并
遇到```removeRange()``` 我们先把要删掉的range加进map里面 然后再删掉
## Code

class RangeModule {
    TreeMap<Integer, Integer> map;

    public RangeModule() {
        map = new TreeMap<>();
    }
    
    public void addRange(int left, int right) {
        while(true){
            Map.Entry<Integer, Integer> entry = map.floorEntry(right);
            if(entry==null || entry.getValue()<left) break;
            left = Math.min(left, entry.getKey());
            right = Math.max(right, entry.getValue());
            map.remove(entry.getKey());
        }
        map.put(left, right);
    }
    
    public boolean queryRange(int left, int right) {
        Map.Entry<Integer, Integer> entry = map.floorEntry(left);
        return entry!=null && entry.getValue()>=right;
    }
    
    public void removeRange(int left, int right) {
        addRange(left, right);
        Map.Entry<Integer, Integer> entry = map.floorEntry(left);
        map.remove(entry.getKey());
        if(entry.getKey()<left) map.put(entry.getKey(), left);
        if(right<entry.getValue()) map.put(right, entry.getValue());
    }
}