系列文章

【英雄哥六月集训】第 01天:数组

【英雄哥六月集训】第 02天:字符串

【英雄哥六月集训】第 03天:排序

【英雄哥六月集训】第 04天:贪心

【英雄哥六月集训】第 05天: 双指针

【英雄哥六月集训】第 06天:滑动窗口

【英雄哥六月集训】第 07天:哈希

【英雄哥六月集训】第 08天:前缀和

【英雄哥六月集训】第 09天:二分查找

【英雄哥六月集训】第 10天: 位运算

【英雄哥六月集训】第 11天: 矩阵

【英雄哥六月集训】第 12天: 链表

【英雄哥六月集训】第 13天: 双向链表

【英雄哥六月集训】第 14天: 栈

【英雄哥六月集训】第 15天: 二叉树

【英雄哥六月集训】第 16天: 队列

【英雄哥六月集训】第 17天: 广度优先搜索

【英雄哥六月集训】第 18天: 树

【英雄哥六月集训】第 19天: 二叉树

【英雄哥六月集训】第 20天: 二叉搜索树

【英雄哥六月集训】第 21天: 堆(优先队列)

【英雄哥六月集训】第 22天: 有序集合

【英雄哥六月集训】第 23天: 字典树

【英雄哥六月集训】第 24天: 线段树

---

线段树

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

一、 我的日程安排表 II

731. 我的日程安排表 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);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

二、 掉落的方块

699. 掉落的方块

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;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

总结