线段树

### 题单

[线段树详解「汇总级别整理 🔥🔥🔥」](https://leetcode.cn/problems/range-module/solutions/1612955/by-lfool-eo50/)

715. Range 模块

C++ 中的 map 底层是平衡二叉树，契合线段树的数据结构。

class RangeModule {
private:
    map<int, int> intervals;
public:
    RangeModule() {}

    void addRange(int left, int right) {
        auto it = intervals.upper_bound(left);
        if (it != intervals.begin()) {
            // not empty
            auto prev_it = prev(it);
            if (prev_it->second >= right) {
                return;
            }
            if (prev_it->second >= left) {
                left = prev_it->first;
                intervals.erase(prev_it);
            }
        }
        while (it != intervals.end() && it->first <= right) {
            right = max(right, it->second);
            it = intervals.erase(it);
        }
        intervals[left] = right;
    }

    bool queryRange(int left, int right) {
        auto it = intervals.upper_bound(left);
        if (it == intervals.begin()) {
            // empty
            return false;
        }
        auto prev_it = prev(it);
        return right <= prev_it->second;
    }

    void removeRange(int left, int right) {
        auto it = intervals.upper_bound(left);
        if (it != intervals.begin()) {
            // not empty
            auto prev_it = prev(it);
            int prev_right = prev_it->second;
            if (prev_right >= right) {
                if (prev_it->first == left) {
                    intervals.erase(prev_it);
                } else {
                    prev_it->second = left;
                }
                if (prev_right > right) {
                    intervals[right] = prev_right;
                }
                return;
            } else if (prev_right > left) {
                if (prev_it->first == left) {
                    intervals.erase(prev_it);
                } else {
                    prev_it->second = left;
                }
            }
        }
        while (it != intervals.end() && it->first < right) {
            if (it->second <= right) {
                it = intervals.erase(it);
            } else {
                intervals[right] = it->second;
                intervals.erase(it);
                return;
            }
        }
    }
};

729. 我的日程安排表 I

class MyCalendar {
private:
    map<int, int> intervals;
public:
    MyCalendar() {}

    bool book(int start, int end) {
        auto it = intervals.upper_bound(start);
        if (it != intervals.begin()) {
            auto last_it = prev(it);
            if (last_it->second > start) {
                return false;
            }
        }
        if (it != intervals.end()) {
            if (it->first < end) {
                return false;
            }
        }
        intervals[start] = end;
        return true;
    }
};

731. 我的日程安排表 II

关于 Pair 里的元素含义：

• first 是区间最大值，second 是懒标记。
• second  只有给定索引区间全覆盖时才会  += val，而全覆盖的情况可能发生在长区间或短区间上
• 每次添加  val  都会分布在不同的  idx(层数有高有低，某个  idx  有加，他的孩子可能之前也有加) 的  second  上，需要每个  idx  维护一个  first  来标识该  idx  下索引区间的最大值。

class MyCalendarTwo {
    unordered_map<int, pair<int, int>> tree;
public:
    MyCalendarTwo() {}

    void update(int start, int end, bool isAdd, int l, int r, int index) {
        int val = isAdd ? 1 : -1;
        if (r < start || l > end) {
            return;
        }
        if (start <= l && r <= end) {
            tree[index].first += val;
            tree[index].second += val;
        } else {
            int mid = (l + r) >> 1;
            update(start, end, isAdd, l, mid, 2 * index);
            update(start, end, isAdd, mid + 1, r, 2 * index + 1);
            tree[index].first = tree[index].second + max(tree[2 * index].first, tree[2 * index + 1].first);
        }
    }

    bool book(int start, int end) {
        update(start, end - 1, true, 0, 1e9, 1);
        if (tree[1].first > 2) {
            update(start, end - 1, false, 0, 1e9, 1);
            return false;
        }
        return true;
    }
};

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