线段树模板

参考：详解线段树
这里暂时不详解线段树了，等自己再明白点再写吧，板子是这样，就是和二叉树概念差不多。需要根据题目的需要，定义节点的值。

线段树模板【动态开点】

从刷题后的运行时间来看，耗时挺大，不知道什么原因导致，（是因为动态开点的原因吗）。

// 基于求「区间和」以及对区间进行「加减」的更新操作，且为「动态开点」
struct Node {
    Node *left,*right;
    int val,lazy;
    Node():val(0),lazy(0),left(nullptr),right(nullptr){}
};
const int N = 1e9;
Node *root = new Node();
void update(Node *node, int start, int end,int l, int r, int val) {
    if(l<=start && r>=end) {
        node->val += (end - start + 1) * val; 
        node->lazy += val; 
        return;
    }
    int mid = (start + end) >> 1;// 右移除2
    pushDown(node, mid-start+1, end-mid);
    if(l <= mid) update(node->left, start, mid, l, r, val); //[start,mid] [l,r] 有交集
    if(r > mid) update(node->right, mid + 1, end, l, r, val); //[l,r] [mid+1,end] 有交集
    pushUp(node); 
}
void pushDown(Node *node, int leftNum, int rightNum) {
    if(node->left==NULL) node->left = new Node();
    if(node->right==NULL) node->right = new Node();
    if(node->lazy==0) return; // 不需要向下更新
    node->left->val += node->lazy * leftNum;
    node->right->val += node->lazy * rightNum;
    node->left->lazy += node->lazy; 
    node->right->lazy += node->lazy; 
    node->lazy = 0;
}
void pushUp(Node *node) {
    node->val = node->left->val + node->right->val;
}
int query(Node *node, int start, int end, int l, int r) {
    if(l<=start && r>=end) return node->val;
    int mid = (start + end) >> 1, ans = 0;
    pushDown(node, mid-start+1, end-mid);
    if(l<=mid) ans += query(node->left, start, mid, l, r);
    if(r>mid) ans += query(node->right, mid+1, end, l, r);
    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

729. 我的日程安排表 I

线段树版本400ms

class MyCalendar {
public:
    MyCalendar() {
    }
    bool book(int start, int end) {
        if(query(root,0,N,start,end-1)!=0) return false;
        update(root,0,N,start,end-1,1);
        return true;

    }
        struct Node {
        Node *left,*right;
        int val,lazy;
        Node():val(0),lazy(0),left(nullptr),right(nullptr){}
    };
    const int N = 1e9;
    Node *root = new Node();
    void update(Node *node, int start, int end,int l, int r, int val) {
        if(l<=start && r>=end) {
            node->val += val; // 每个节点存的是当前区间的最大值
            node->lazy += val; //懒惰标记，标记该节点下的子节点需要更新，用于遍历到时候在更新，
            return;
        }
        pushDown(node);
        int mid = (start + end) >> 1;// 右移除2
        if(l <= mid) update(node->left, start, mid, l, r, val); //[start,mid] [l,r] 有交集
        if(r > mid) update(node->right, mid+1, end, l, r, val); //[l,r] [mid+1,end] 有交集
        pushUp(node); 
    }
    void pushDown(Node *node) {
        if(node->left==NULL) node->left = new Node();
        if(node->right==NULL) node->right = new Node();
        if(node->lazy==0) return; // 不需要向下更新
        node->left->val += node->lazy;
        node->right->val += node->lazy;
        node->left->lazy += node->lazy; 
        node->right->lazy += node->lazy; 
        node->lazy = 0;
    }
    void pushUp(Node *node) {
        // 每个节点存的是当前区间的最大值
        node->val = max(node->left->val, node->right->val);
    }
    int query(Node *node, int start, int end, int l, int r) {
        if(l<=start && r>=end) return node->val;
        pushDown(node);
        int mid = (start + end) >> 1, ans = 0;
        if(l<=mid) ans = query(node->left,start,mid,l,r);
        if(r>mid) ans = max(query(node->right,mid+1,end,l,r),ans);
        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

set二分版本64ms

class MyCalendar {
    set<pair<int, int>> booked;

public:
    bool book(int start, int end) {
        auto it = booked.lower_bound({end, 0});
        if (it == booked.begin() || (--it)->second <= start) {
            booked.emplace(start, end);
            return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

731. 我的日程安排表 II

线段树版本

class MyCalendarTwo {
public:
    MyCalendarTwo() {

    }
    
    bool book(int start, int end) {
        if(query(root, 0, N, start, end-1) == 2) return false;
        update(root, 0, N, start, end-1, 1);
        return true;
    }
    struct Node {
        Node *left,*right;
        int val,lazy;
        Node():val(0),lazy(0),left(nullptr),right(nullptr){}
    };
    const int N = 1e9;
    Node *root = new Node();
    void update(Node *node, int start, int end,int l, int r, int val) {
        if(l<=start && r>=end) {
            node->val += val; // 每个节点存的是当前区间的最大值
            node->lazy += val; //懒惰标记，标记该节点下的子节点需要更新，用于遍历到时候在更新，
            return;
        }
        pushDown(node);
        int mid = (start + end) >> 1;// 右移除2
        if(l <= mid) update(node->left, start, mid, l, r, val); //[start,mid] [l,r] 有交集
        if(r > mid) update(node->right, mid+1, end, l, r, val); //[l,r] [mid+1,end] 有交集
        pushUp(node); 
    }
    void pushDown(Node *node) {
        if(node->left==NULL) node->left = new Node();
        if(node->right==NULL) node->right = new Node();
        if(node->lazy==0) return; // 不需要向下更新
        node->left->val += node->lazy;
        node->right->val += node->lazy;
        node->left->lazy += node->lazy; 
        node->right->lazy += node->lazy; 
        node->lazy = 0;
    }
    void pushUp(Node *node) {
        // 每个节点存的是当前区间的最大值
        node->val = max(node->left->val, node->right->val);
    }
    int query(Node *node, int start, int end, int l, int r) {
        if(l<=start && r>=end) return node->val;
        pushDown(node);
        int mid = (start + end) >> 1, ans = 0;
        if(l<=mid) ans = query(node->left,start,mid,l,r);
        if(r>mid) ans = max(query(node->right,mid+1,end,l,r),ans);
        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

差分版本

class MyCalendarTwo {
public:
    map<int,int> mp;
    MyCalendarTwo() {
        mp.clear();
    }
    
    bool book(int start, int end) {
        mp[start]+=1; mp[end]-=1;
        int ans = 0, sum = 0;
        for(auto &it:mp) {
            sum+=it.second;
            ans = max(ans,sum);
        }
        if(ans==3) {
            mp[start]-=1;
            mp[end]+=1;
            return false;
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

732. 我的日程安排表 III

线段树版本248ms

class MyCalendarThree {
public:
    int ans = 0;
    MyCalendarThree() {

    }
    
    int book(int start, int end) {
        update(root,0,N,start,end-1,1);
        ans = max(query(root,0,N,start,end-1),ans);
        return ans;
    }
    struct Node {
        Node *left,*right;
        int val,lazy;
        Node():val(0),lazy(0),left(nullptr),right(nullptr){}
    };
    const int N = 1e9;
    Node *root = new Node();
    void update(Node *node, int start, int end,int l, int r, int val) {
        if(l<=start && r>=end) {
            node->val += val; // 每个节点存的是当前区间的最大值
            node->lazy += val; //懒惰标记，标记该节点下的子节点需要更新，用于遍历到时候在更新，
            return;
        }
        pushDown(node);
        int mid = (start + end) >> 1;// 右移除2
        if(l <= mid) update(node->left, start, mid, l, r, val); //[start,mid] [l,r] 有交集
        if(r > mid) update(node->right, mid+1, end, l, r, val); //[l,r] [mid+1,end] 有交集
        pushUp(node); 
    }
    void pushDown(Node *node) {
        if(node->left==NULL) node->left = new Node();
        if(node->right==NULL) node->right = new Node();
        if(node->lazy==0) return; // 不需要向下更新
        node->left->val += node->lazy;
        node->right->val += node->lazy;
        node->left->lazy += node->lazy; 
        node->right->lazy += node->lazy; 
        node->lazy = 0;
    }
    void pushUp(Node *node) {
        // 每个节点存的是当前区间的最大值
        node->val = max(node->left->val, node->right->val);
    }
    int query(Node *node, int start, int end, int l, int r) {
        if(l<=start && r>=end) return node->val;
        pushDown(node);
        int mid = (start + end) >> 1, ans = 0;
        if(l<=mid) ans = query(node->left,start,mid,l,r);
        if(r>mid) ans = max(query(node->right,mid+1,end,l,r),ans);
        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

差分版本88ms

class MyCalendarThree {
public:
    // max cross time times
    map<int,int> mp;
    MyCalendarThree() {
        mp.clear();
    }
    int book(int start, int end) {
        mp[start]+=1;mp[end]-=1;
        int ans = 0,sum = 0;
        for(auto &it:mp) {
            sum+=it.second;
            ans = max(sum,ans);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18