[数据结构与算法]「LeetCode」统计区间中的整数数目 动态开点线段树模板

原题链接

贴个模板以备以后不时之需 😋

class CountIntervals {
    
    public SegmentTree t;

    public CountIntervals() {
        t=new SegmentTree(1,1000000000);
    }
    
    public void add(int left, int right) {
        t.change(t.root,left,right);
    }
    
    public int count() {
        return t.root.sum;
    }
    
    static class SegmentTree{
    	class Node{
    		int l;
    		int r;
    		int sum;
            int tag;
            Node lchild;
            Node rchild;
    		
    		public Node(int l,int r) {
    			this.l=l;
    			this.r=r;
    		}
            
            public Node(int l,int r,int tag,int sum){
                this.l=l;
    			this.r=r;
                this.tag=tag;
                this.sum=sum;
            }
    	}
    	public Node root;
        
        public SegmentTree(int l,int r){
            root=new Node(l,r);
        }
        
        
        public void pushUp(Node cur){
            cur.sum=0;
            if(cur.lchild!=null)
                cur.sum+=cur.lchild.sum;
            if(cur.rchild!=null)
                cur.sum+=cur.rchild.sum;
        }
    	
    	public void  pushDown(Node cur) {
            if(cur.tag!=0){
                int mid=(cur.l+cur.r)/2;
                if(cur.lchild==null)
                    cur.lchild=new Node(cur.l,mid,cur.tag,mid-cur.l+1);
                else{
                    cur.lchild.tag=cur.tag;
                    cur.lchild.sum=(cur.lchild.r-cur.lchild.l+1);
                }
                if(cur.rchild==null)
                    cur.rchild=new Node(mid+1,cur.r,cur.tag,cur.r-mid);
                else{
                    cur.rchild.tag=cur.tag;
                    cur.rchild.sum=(cur.rchild.r-cur.rchild.l+1);
                }
            }
    	}
    	
    	
    	public void change(Node cur,int l,int r) {
    		if(cur.l>=l&&cur.r<=r) {
    			cur.tag=1;
    			cur.sum=cur.r-cur.l+1;
    			return ;
    		}
    		pushDown(cur);
    		int mid=(cur.l+cur.r)/2;
    		if(l<=mid){
                if(cur.lchild==null)
                    cur.lchild=new Node(cur.l,mid,0,0);
    			change(cur.lchild,l,r);
            }
    		if(r>mid){
                if(cur.rchild==null)
                    cur.rchild=new Node(mid+1,cur.r,0,0);
    			change(cur.rchild,l,r);
            }
            pushUp(cur);
    	}
    	
    }
}

/**
 * Your CountIntervals object will be instantiated and called as such:
 * CountIntervals obj = new CountIntervals();
 * obj.add(left,right);
 * int param_2 = obj.count();
 */

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖