线段树复习 ①

前情提要

线段树实在是太难了，今天又做到一题，已经完全想不起来怎么做了，所以复习了一下。以后每次做到又不会了就复习一下，把例题收录进来。不喜欢背代码模板，就把这次悟到的用文字描述一下吧。

修改函数 update()

• 需要六个参数，其中两个表示待查找的区间的左右边界，两个表示当前查找到的区间的左右边界（初始值为整棵线段树的左界和右界），一个表示当前节点的下标，最后一个表示需要修改的值（下面这道题中需要修改的值固定为 1 ，所以可以省去一个参数）。

• 如果当前区间和待查找区间不重叠，则直接返回。

• 如果当前区间被待查找区间完全包含，则修改本节点的值后为当前节点打下一个 lazytag ，表示这个节点后的所有节点都要加上 lazytag 的值。

• 如果当前区间和待查找区间只有部分重叠，则将当前区间一分为二，并递归地进行搜索，相当于搜索当前节点的左右两个子节点。递归搜索完毕后，用两个子节点的值更新当前节点的值。

别的暂时还没什么更深入的理解，下次再更新。

---

例题

LeetCode 732. 我的日程安排表 III

当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。

给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

• MyCalendarThree() 初始化对象。

• int book(int start, int end) 返回一个整数 k，表示日历中存在的 k 次预定的最大值

示例：

输入：
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, 1, 1, 2, 3, 3, 3]

解释：
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

---

题解

由于本题 start 和 end 的数据范围很大，所以如果像之前那样暴力开 4 倍内存的话内存会溢出。所以本题中可以用哈希表来代替数组。

代码：

class MyCalendarThree {
private:
    unordered_map<int, int> tree;
    unordered_map<int, int> lazy;
    void update(int start, int end, int l, int r, int node) {
        if (start > r || end < l) return;//如果当前处理范围在需要计算的范围之外，则直接返回。
        else if (start <= l && r <= end) {
            //如果当前处理范围被需要计算的范围完全包括，则将整个节点打上一个lazytag，并将节点值加一。
            tree[node]++;
            lazy[node]++;
        }
        else {
            int leftnode = node * 2;
            int rightnode = node * 2 + 1;
            int mid = (l + r) / 2;
            update(start, end, l, mid, leftnode);
            update(start, end, mid + 1, r, rightnode);
            tree[node] = lazy[node] + max(tree[leftnode], tree[rightnode]);
        }
    }
public:
    MyCalendarThree() {

    }

    int book(int start, int end) {
        update(start, end - 1, 0, 1e9, 1);
        return tree[1];
    }
}; 

代码中，用 start 和 end 表示待处理的区间，用l 和 r 表示当前处理的区间。在刚开始阅读这段代码的时候我很奇怪为什么一开始打上 lazytag 的时候 node 的值已经加上一了，后面重新计算的时候还要再加 lazytag 的值，后来发现每个 node 储存的值是区间的最大值，而重新计算 node 值时它的 leftnode 和 rightnode 是没有把 lazytag 的值算上的，所以要重新加上一遍。

---

有的没的

忙着干活，没空写了，下次一定。