715. Range Module

Sep 14, 2021

Leetcode

Basic Idea

基本思路有两个，一个是使用SegmentTree，还有一个是使用TreeMap。

TreeMap Solution

利用TreeMap排序的性质，维持merge interval的操作，在其中存放互不重叠的interval。利用 TreeMap.subMap(left, true, right, false) 来删掉中间overlap的小区间。

SegmentTree Solution

对于SegmentTree我之前的印象一直是需要和总数据量一样大的空间和时间，但事实上并不需要。在query的时候如果当前的node没有child，则说明child的性质和当前的node相同，可以直接返回。只有在更新的时候需要按需求populate 左右node。

class RangeModule {

    SegmentTree tree;
    
    public RangeModule() {
        this.tree = new SegmentTree(1, (int) 1e9);
    }
    
    public void addRange(int left, int right) {
        tree.update(left, right - 1, true);
    }
    
    public boolean queryRange(int left, int right) {
        return tree.query(left, right - 1);
    }
    
    public void removeRange(int left, int right) {
        tree.update(left, right - 1, false);
    }
    
    private static class SegmentTree {
        private static class TreeNode {
            TreeNode left, right;
            int start, end;
            boolean tracked;
            
            TreeNode(int start, int end, boolean tracked) {
                this.start = start;
                this.end = end;
                this.tracked = tracked;
            }
        }
        
        private TreeNode root;
        
        SegmentTree(int left, int right) {
            this.root = new TreeNode(left, right, false);
        }
        
        boolean query(int left, int right) {
            return query(left, right, root);
        }
        
        void update(int left, int right, boolean tracked) {
            update(left, right, tracked, root);
        }
        
        private boolean query(int left, int right, TreeNode node) {
            if (node.left == null) {
                // 此时该node没有孩子，表示该范围内所有interval状态相同
                return node.tracked;
            }
            int mid = (node.start + node.end) / 2;
            boolean ret = true;
            if (right <= mid) {
                return query(left, right, node.left);
            } else if (left > mid) {
                return query(left, right, node.right);
            } else {
                return query(left, mid, node.left) & query(mid + 1, right, node.right);
            }
        }
        
        private void update(int left, int right, boolean tracked, TreeNode node) {
            if (left == node.start && right == node.end) {
                node.left = null;
                node.right = null;
                node.tracked = tracked;
                return;
            }
            int mid = (node.start + node.end) / 2;
            // 这里延迟populate左右孩子，状态初始化为和parent相同
            if (node.left == null) {
                node.left = new TreeNode(node.start, mid, node.tracked);
                node.right = new TreeNode(mid + 1, node.end, node.tracked);
            }
            if (left <= mid) {
                update(left, Math.min(right, mid), tracked, node.left);
            }
            if (right > mid) {
                update(Math.max(mid + 1, left), right, tracked, node.right);
            }
            node.tracked = node.left.tracked & node.right.tracked;
        }
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * boolean param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */