# rangelist

**Repository Path**: bernard5/rangelist

## Basic Information

- **Project Name**: rangelist
- **Description**: GitLab 笔试
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-05-07
- **Last Updated**: 2023-09-14

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# RangeList

这是本人应试GitLab的校招实习笔试解决方案仓库。[GitLab提供的题目](./RangeList.pdf)要求我在72小时内以Ruby/Go完善一份代码，主要内容是实现一个类以维护区间合并下的区间增删查。

在我完成了《CSAPP》的学习和[全部实验](https://gitee.com/bernard5/csapp-lab)后，我意识到这题其实是对显式内存分配器的一种抽象。区间增删对应的分别是`malloc`和`free`。

## 关于题目

- 如果**增删操作较少，输出操作很多**，直接数组模拟即可，可以对增删操作进行的优化是二分定位，但即使如此，单次增删操作最坏情况（移动整个数组）的复杂度依然是 ${O(n)}$：二分操作 ${O(\log n)}$，区间合并、增加的复杂度为 ${O(n)}$
- 如果**增删操作很多，输出操作较少**，在区间端点取值较小的情况下，**前缀和+差分**是一个不错的解决方案，它需要全区间长度量级的空间，增删操作复杂度 ${O(1)}$，输出区间复杂度 ${O(n)}$。当区间端点的最小值和最大值相差较大时，如果输出操作较少，允许离线的话，可以用**离散化**的做法，将所需空间从全区间长度量级缩小为区间数量的量级。

如果不允许离线的话，可以考虑以下数据结构：

1. Treap树
2. 珂朵莉树
3. 跳表

由于时间所限，本次我采用的数据结构是**珂朵莉树**，这是一种**基于红黑树**的数据结构，单次增删操作的复杂度是${O(\log n)}$，遍历输出的复杂度是${O(n\log n)}$。

上述三种数据结构时间复杂度接近，对于增删操作而言，Treap树的时间常数最小，跳表的时间常数最大。

理论上说Treap树可以降低常数，但可能会码量会上升，可维护性也会下降。

考虑将题目转化为如下情况：
1. 由于题目中区间端点均为整数且均为左闭右开区间，所以可将区间端点转换成左闭右闭，以减少连接等情况的考虑，亦可减少冗余代码。
2. 一根近似无限长数轴的区间颜色覆盖问题，颜色只有黑白，初始整个数轴均为白色，增区间等效于覆盖黑色，删区间等效于覆盖白色。

也就是这道题：[CF915E Physical Education Lessons](https://codeforces.com/contest/915/problem/E)

## 算法竞赛风格的C++代码

由于C++是我比较顺手的语言（而且也有方便可靠的STL），先写了一份算法竞赛风格的C++代码作为预研。

由于题目没有给定数据范围，假定区间端点在int32的正数范围内。

```cpp
#include <iostream>
#include <set>
class RangeList {
    struct node {  // 存储区间的单个节点
        int l, r;
        mutable bool v;
        bool operator<(const node& o) const { return l < o.l; }
    };
    std::set<node> tree;
    const int leftBound = 1;   // 数轴左边界
    const int rightBound = INT_MAX;  // 数轴右边界
    inline std::set<node>::iterator split(int pos) {  // 返回以pos为左端点的区间的迭代器
        std::set<node>::iterator it = tree.lower_bound(
            node{pos, 0, 0});  // 寻找左端点大于等于pos的第一个区间
        if (it != tree.end() && it->l == pos)
            return it;  // 如果已经存在以pos为左端点的区间，直接返回
        --it;           // 否则往前数一个区间
        if (it->r < pos) return tree.end();  // 区间无交
        int l = it->l, r = it->r;
        bool v = it->v;
        tree.erase(it);
        tree.insert(node{l, pos - 1, v});  // 拆分
        return tree.insert(node{pos, r, v}).first;
    }
    inline void assign(int l, int r, bool v) {  // 给区间[l, r)上色v
        std::set<node>::iterator itr = split(r), itl = split(l);
        tree.erase(itl, itr);
        tree.insert(node{l, r - 1, v});
    }

   public:
    RangeList() {  // 初始整个数轴均为白色
        tree.insert(node{leftBound, rightBound, 0});
    }
    void Add(int l, int r) {  // 增区间等效于覆盖黑色
        assign(l, r, 1);
    }
    void Remove(int l, int r) {  // 删区间等效于覆盖白色
        assign(l, r, 0);
    }
    void Print() {  // 在输出时完成区间合并
        int l = -1, r = -1;
        for (node segment : tree) {
            if (segment.v) {
                if (l == -1)
                    l = segment.l, r = segment.r;
                else if (segment.l == r + 1) {
                    r = segment.r;
                } else {
                    std::cout << "[" << l << "," << r + 1 << ") ";
                    l = segment.l, r = segment.r;
                }
            } else {
                if (l != -1) std::cout << "[" << l << "," << r + 1 << ") ";
                l = -1;
            }
        }
        if (l != -1) std::cout << "[" << l << "," << r + 1 << ") ";
        std::cout << '\n';
    }
};
int main() {
    RangeList rl;
    rl.Add(1, 5);
    rl.Print();

    rl.Add(10, 20);
    rl.Print();

    rl.Add(20, 20);
    rl.Print();

    rl.Add(20, 21);
    rl.Print();

    rl.Add(2, 4);
    rl.Print();

    rl.Add(3, 8);
    rl.Print();

    rl.Remove(10, 10);
    rl.Print();

    rl.Remove(10, 11);
    rl.Print();

    rl.Remove(15, 17);
    rl.Print();

    rl.Remove(3, 19);
    rl.Print();

    return 0;
}
```

## 总结

1. 我的代码的优点是使用了较优的数据结构，时空复杂度较好：平均时间复杂度插入/删除$O(\log n)$，输出$O(n \log n)$，空间复杂度$O(n)$，和插入/删除次数成正比。
2. 有待提升的地方是如果在遍历打印时做区间合并，可以在某些情况下降低存储所需空间。