珂朵莉树——维护连续区间

(Updated: )
(4 mins to read)

随机数据区间赋值

用set维护所有不相交的值相同的区间段。初始时，需要for (i = 1; i <= n; i++) odt.emplace(i, i, a[i])。

split(x)返回以x起始的区间对应的迭代器。

split(r + 1), split(l)就可以得到[l, r]区间对应的迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int n;
struct Node {
    int l, r;
    mutable int v;
    explicit Node(int l_, int r_=-1, int v_=0) : l(l_), r(r_), v(v_) {}
    bool operator<(const Node& oth) const { return l < oth.l; }
};
set<Node> odt;
set<Node>::iterator split(int x) {
    if (x > n) return odt.end();
    auto it = --odt.upper_bound(Node(x));
    if (it->l == x) return it;
    int l = it->l, r = it->r, v = it->v;
    odt.erase(it);
    odt.emplace(l, x - 1, v);
    return odt.emplace(x, r, v).first;
}

区间插入、删除

Leetcode 2276. 统计区间中的整数数目。

插入区间，查询当前区间覆盖的整数个数。

思路：套用珂朵莉树的框架，用split(x)得到左端点大于等于x的第一个区间（因为初始区间是空的，不能保证存在包含x的区间）。

  • 插入：不断往前遍历删除与插入区间有交集的区间（注意完全包含和有交集两种case），最后再插入即可
  • 删除：不断往前遍历删除与插入区间有交集的区间（注意完全包含和有交集两种case）

维护连续区间，并支持快速插入和删除的题目都可以尝试套用split这个抽象函数。

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
class CountIntervals {
public:
    CountIntervals() {}
    
    void add(int left, int right) {
        auto it2 = split(right + 1);
        auto it1 = it2;
        while (it1 != st.begin() && prev(it1)->second <= right && prev(it1)->second >= left) {
            --it1;
            sz -= it1->second - it1->first + 1;
            if (it1->first < left) {
                left = it1->first;
            }
        }   
        st.erase(it1, it2);
        st.emplace(left, right);
        sz += right - left + 1;
    }
    
    int count() {
        return sz;
    }

private:
    set<pair<int, int>>::iterator split(int x) {
        auto it = st.upper_bound({x, -1});
        if (it == st.begin()) return it;
        if (prev(it)->first == x || prev(it)->second < x) return it;
        --it;
        int l = it->first, r = it->second;
        st.erase(it);
        st.emplace(l, x - 1);
        return st.emplace(x, r).first;
    }

    set<pair<int, int>> st;
    int sz{0};
};