当前位置：网站首页>[brother hero June training] day 24: line segment tree

Line segment tree is a binary search tree , Similar to interval trees , It divides an interval into some cell intervals , Each cell interval corresponds to a leaf node in the line segment tree .
Using line segment tree can quickly find the number of times a node appears in several line segments , The time complexity is O(logN). The unoptimized space complexity is 2N, In practical application, it usually needs to be opened 4N To avoid crossing the bounds , So sometimes discretization is needed to compress space .

One 、 My schedule II

731. My schedule II

class MyCalendarTwo {
    
    TreeMap<Integer,Integer> delta;

    public MyCalendarTwo() {
    
        delta = new TreeMap();
    }
    
    public boolean book(int start, int end) {
    
        delta.put(start,delta.getOrDefault(start,0)+1);
        delta.put(end, delta.getOrDefault(end, 0)-1);

        int active = 0;
        for( int d:delta.values()){
    
            active +=d;
            if(active >=3){
    
                delta.put(start, delta.get(start)-1);
                delta.put(end, delta.get(end)+1);
                if(delta.get(start)==0)
                    delta.remove(start);
                return false;
                
            }
        }
        return true;
    }
}

/** * Your MyCalendarTwo object will be instantiated and called as such: * MyCalendarTwo obj = new MyCalendarTwo(); * boolean param_1 = obj.book(start,end); */

Two 、 Falling diamonds

699. Falling diamonds

class Solution {
    
    class Node{
    
        int ls,rs,val,add;
    }
    int N = (int)1e9,cnt=0;
    Node[] tr= new Node[1000010];
    void update(int u,int lc,int rc,int l,int r,int v){
    
        if( l<= lc && rc<= r){
    
            tr[u].val=v;
            tr[u].add=v;
            return ;
        }
        pushdown(u);
        int mid= lc+rc >>1;
        if(l<= mid) update(tr[u].ls,lc,mid,l,r,v);
        if(r>mid) update(tr[u].rs,mid+1,rc,l,r,v);
        pushup(u);
    }
    int query(int u,int lc,int rc,int l,int r){
    
        if(l<=lc && rc<=r) return tr[u].val;
        pushdown(u);
        int mid = lc+rc >>1,ans=0;
        if(l<=mid) ans = query(tr[u].ls,lc,mid,l,r);
        if(r>mid) ans = Math.max(ans, query(tr[u].rs,mid+1,rc,l,r));
        return ans;

    }
    void pushdown(int u){
    
        if(tr[u]==null) tr[u]=new Node();
        if(tr[u].ls ==0){
    
            tr[u].ls=++cnt;
            tr[tr[u].ls]=new Node();
        }
        if(tr[u].rs ==0){
    
            tr[u].rs=++cnt;
            tr[tr[u].rs]=new Node();
        }
        if(tr[u].add == 0) return ;
        int add = tr[u].add;
        tr[tr[u].ls].add = add; 
        tr[tr[u].rs].add = add;
        tr[tr[u].ls].val = add; 
        tr[tr[u].rs].val = add;
        tr[u].add=0;

    }
    void pushup(int u){
    
        tr[u].val=Math.max(tr[tr[u].ls].val,tr[tr[u].rs].val);
    }
    public List<Integer> fallingSquares(int[][] positions) {
    
        List<Integer> ans = new ArrayList<>();
        tr[1] = new Node();
        for(int[] info:positions){
    
            int x = info[0], h = info[1], cur = query(1,1,N,x,x+h-1);
            update(1,1,N,x,x+h-1,cur+h);
            ans.add(tr[1].val);
        }
        return ans;

    }
}