Range模块：维护区间的增删改查

字数统计: 3k字 | 阅读时长: 12分

2023-11-12

摘要: 基于平衡树的Range模块，维护区间的增删改查

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们通过力扣 715 来看一下可以动态维护区间的增删改查的组件的功能与实现，本题的代码可以作为模板使用，在需要动态维护区间的问题中会用到。

区间模块经常根扫描线算法配合处理矩形问题：横轴区间的左右端点作为两种事件，合适地排序，然后用扫描线算法对事件扫描。对依次到来的事件，用区间模块对竖轴上的区间做相应操作。类本文我们将用区间模块的代码模板解决 699. 掉落的方块。类似思路的题目还有：

模板题：715. Range 模块

Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。

半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。

实现 RangeModule 类:

RangeModule() 初始化数据结构的对象。

void addRange(int left, int right) 添加半开区间 [left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true ，否则返回 false 。
void removeRange(int left, int right) 停止跟踪半开区间 [left, right) 中当前正在跟踪的每个实数。

提示：

1 2	1 <= left < right <= 1e9 在单个测试用例中，对 addRange 、 queryRange 和 removeRange 的调用总数不超过 1e4 次

示例 1：
输入
[“RangeModule”, “addRange”, “removeRange”, “queryRange”, “queryRange”, “queryRange”]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
输出
[null, null, null, true, false, true]
解释
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); 返回 true （区间 [10, 14) 中的每个数都正在被跟踪）
rangeModule.queryRange(13, 15); 返回 false（未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字）
rangeModule.queryRange(16, 17); 返回 true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）

算法：平衡树

在一些问题中，我们需要动态低维护区间，在插入区间时，动态地降重叠的部分合并；删除的时候，只删与被删区间重叠的部分，已有区间中未于被删区间重叠的部分需要保留。

对于已有的若干半开区间 [ai, bi)，如果将其按照左端点排序，这样插入新区间时，可以快速找到所有重叠的区间，然后将所有重叠的区间合并到一起。这个过程参考文章区间合并问题。在删除区间时，也可以快速找到所有的重叠区间，将重叠的部分删去。在插入和删除过程中需要始终维护 Ranges 模块中的区间无重叠。本题要实现的正是这样的功能。

整个过程的关键点是在插入删除时需要保持区间的有序性，从而在插入或删除区间之前，可以快速找到所有重叠区间。因此自然想到用平衡树来维护。

用一个 TreeMap 来维护所有的区间：

1 2	map<int, int> ranges_; using IT = map<int, int>::iterator;

在插入区间 [left, right)、删除区间 [left, right)、查询区间 [left, right) 前，都要首先在平衡树中找到与 [left, right) 重叠的部分。这个功能抽象出来，供插入、删除、查找时使用，接口如下：

void getoverlapranges(int left, int right, IT& l, IT& r)
{
    l = ranges_.upper_bound(left);
    r = ranges_.upper_bound(right);
    if(l != ranges_.begin())
        if((--l) -> second < left) 
            l++;
}

返回两个迭代器 [l, r) 表示平衡树中与 [left, right) 重叠的区间所在的节点。如果 l == r 则表示没有重叠部分。

对于插入和删除，都是先将 [l, r) 范围删去，然后构造新的区间插入。在删除、构造、插入的过程中注意细节即可。

对于特定的问题，可能需要在找到重叠区间之后先进行一些操作，然后再执行插入删除，因此当区间模块作为组件时，需要根据特定的需求对内部微调一些逻辑。比如在后面的 699. 掉落的方块中，在重叠区间上需要更新最高的高度，而这种更新操作再代码模板里没有，需要自己增加。

代码 (C++)

class RangeModule {
public:
    RangeModule() {}

    void addRange(int left, int right) {
        IT l, r;
        getoverlapranges(left, right, l, r);
        if(l != r) // 至少一个 overlap
        {
            auto last = r;
            --last;
            left = min(left, l -> first);
            right = max(right, last -> second);
            ranges_.erase(l, r);
        }
        // add/merged range
        ranges_[left] = right;
    }

    bool queryRange(int left, int right) {
        IT l, r;
        getoverlapranges(left, right, l, r);
        if(l == r) // 至少一个 overlap
            return false;
        return l -> first <= left && l -> second >= right; // 看第一个 overlap 的区间是不是把输入全包含了
    }

    void removeRange(int left, int right) {
        IT l, r;
        getoverlapranges(left, right, l, r);
        if(l == r) 
            return;
        auto last = r;
        --last;
        int start = min(left, l -> first);
        int end = max(right, last -> second);
        ranges_.erase(l, r);
        if(start < left) 
            ranges_[start] = left;
        if(end > right) 
            ranges_[right] = end;
    }

private:
    using IT = map<int, int>::iterator;
    map<int, int> ranges_;

    void getoverlapranges(int left, int right, IT& l, IT& r)
    {
        l = ranges_.upper_bound(left);
        r = ranges_.upper_bound(right);
        if(l != ranges_.begin())
            if((--l) -> second < left)
                l++;
    }
};

题目：699. 掉落的方块

在二维平面上的 x 轴上，放置着一些方块。

给你一个二维整数数组 positions ，其中 positions[i] = [lefti, sideLengthi] 表示：第 i 个方块边长为 sideLengthi ，其左侧边与 x 轴上坐标点 lefti 对齐。

每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到另一个正方形的顶边或者是 x 轴上。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。

在每个方块掉落后，你必须记录目前所有已经落稳的方块堆叠的最高高度。

返回一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度。

提示：

1
2
3

1 <= positions.length <= 1000
1 <= lefti <= 1e8
1 <= sideLengthi <= 1e6

示例 1：

输入：positions = [[1,2],[2,3],[6,1]]
输出：[2,5,5]
解释：
第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 2 。
第 2 个方块掉落后，最高的堆叠由方块 1 和 2 组成，堆叠的最高高度为 5 。
第 3 个方块掉落后，最高的堆叠仍然由方块 1 和 2 组成，堆叠的最高高度为 5 。
因此，返回 [2, 5, 5] 作为答案。

示例 2：
输入：positions = [[100,100],[200,100]]
输出：[100,100]
解释：
第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 100 。
第 2 个方块掉落后，最高的堆叠可以由方块 1 组成也可以由方块 2 组成，堆叠的最高高度为 100 。
因此，返回 [100, 100] 作为答案。
注意，方块 2 擦过方块 1 的右侧边，但不会算作在方块 1 上着陆。

算法：平衡树

用区间模块 Ranges 记录已经落下过的正方形。

对于一个正方形 [pos, len]，它横跨区间 [pos, pos + len)，如果这个范围此前没有落下过正方形，即区间模块中没有这个范围的记录，则区间模块中可以直接记录。

区间 [pos, pos+len) 的高度为 len。如果此前已经有正方形落在了该区域，则 [pos, pos+len) 会与 Ranges 中的一些已有区间重叠。那么就先要处理这些重叠，重叠可能发生的情况如下：

1 2	[pos, pos+len) [left1, right1) [left2, right2) [left3, right3)

受影响的有若干区间，[pos, pos+len) 最终会更新的高度为这些受影响区间中最高值加上 len。而受影响区间中可能有一部分是在重叠部分之外，

例如上面的区间 [left1, right1) ， [left3, right3)。则非重叠的部分仍然维护这原来的最高值。因此更新流程如下：

step1: 在区间模块中找到所有与 [pos, pos+len) 重叠的区间
step2: 在若干重叠区间中找到两端与 [pos, pos+len) 不重叠的部分，并记录这若干区间的高度最大值
step3: 将这若干个区间全部动 Ranges 模块中删掉
step4: 插入 [pos, pos+len) 的高度记录，为 step2 得到的这一部分的原高度最大值 + len
step5：如果被删的若干重叠区间两侧有与 [pos, pos+len) 不重叠的部分，则把这部分的记录再插入回去
step6: 新插入的高度值与 Ranges 模块中维护的全局最大值比较，将较大这作为本次更新的答案输出.

以上算法中，主要用到的就是：区间在动态的插入删除过程中，插入的时候动态地将重叠部分合并，删除的时候只将重叠部分删掉，已有区间中未与被删区间重叠的部分需要保留。

这个功能用一个 TreeMap 维护，键是区间左端点，值是右端点(开区间)。每次需要插入或者删除新区间时，首先利用左端点的有序性可以快速找到所有的重叠区间，然后在重叠区间上进行操作，本题中是更新最高的高度，然后做插入删除的动作，在插入删除过程中始终维护 Ranges 模块中的区间无重叠。

前面基于 715. Range 模块实现的正是以上功能的组件，只是区间模块作为组件时，在前面代码模板的基础上，需要根据特定的需求对内部微调一些逻辑，微调的部分见前面的分析和后面的代码。

代码 (C++)

class Ranges
{
public:
    Ranges()
    {
        ranges = map<int, PII>();
        max_h = 0;
    }

    int update(int start, int end, int len)
    {
        // [start, end) 范围的 h 最大值, 返回 h
        IT l, r;
        get_overlap(start, end, l, r);
        // [l, r) 为有重叠的区间
        if(l == r) // [start, end) 范围无已有区间
        {
            ranges.insert(PIP(start, PII(end, len)));
            max_h = max(max_h, len);
            return max_h;
        }
        auto last = r;
        --last;

        bool has_left = false, has_right = false;
        int left_l = l -> first;
        int left_r = start;
        int left_h = (l -> second).second;
        int right_l = end;
        int right_r = (last -> second).first;
        int right_h = (last -> second).second;
        if(left_l < left_r)
            has_left = true;
        if(right_l < right_r)
            has_right = true;

        auto iter = l;
        int h = (iter -> second).second;
        ++iter;
        while(iter != r)
        {
            h = max(h, (iter -> second).second);
            ++iter;
        }

        ranges.erase(l, r);
        if(has_left)
            ranges.insert(PIP(left_l, PII(left_r, left_h)));
        if(has_right)
            ranges.insert(PIP(right_l, PII(right_r, right_h)));
        int new_h = h + len;
        ranges.insert(PIP(start, PII(end, new_h)));
        max_h = max(max_h, new_h);
        return max_h;
    }

private:
    using PII = pair<int, int>;
    using PIP = pair<int, PII>;
    using IT = map<int, PII>::iterator;
    map<int, PII> ranges; // left -> (right, h)
    int max_h;

    void get_overlap(int left, int right, IT& l, IT& r)
    {
        l = ranges.upper_bound(left);
        r = ranges.lower_bound(right);
        if(l != ranges.begin())
        {
            --l;
            if((l -> second).first <= left)
                ++l;
        }
    }
};

class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        int n = positions.size();
        vector<int> result(n, -1);
        Ranges ranges;
        for(int i = 0; i < n; ++i)
        {

            int left = positions[i][0];
            int len = positions[i][1];
            int right = left + len; // right 是开区间
            result[i] = ranges.update(left, right, len);
        }
        return result;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法数据结构

Range模块：维护区间的增删改查

模板题：715. Range 模块

算法：平衡树

代码 (C++)

题目：699. 掉落的方块

算法：平衡树

代码 (C++)