ODT学习笔记

ODT 学习笔记

简介

ODT(old drive tree)，又名珂朵莉树，是一种暴力的数据结构，可以解决区间推平操作的一类题目，举个例子，就是把一个序列中 $[l,r]$ 这一个区间的数都修改为 $x$ ，当然，可以用线段树完成，但是如果 $l,r$ 足够大，线段树用不了，而且数据是随机的，就可以用珂朵莉树。

原理

定义

执行推平操作之后，只要推平的区域大于1，就一定会出现一个区间是相同的数字，珂朵莉树就是用set维护这一个区间的一种数据结构

这张图就可以发现，可以把 $1,2;3,5;6,6;7,9$ 分别存入珂朵莉树，这样代码就可以写出

struct node{
	int l,r;										//这里表示这个区间是存储l~r的值
	mutable int v;									//这个值为多少
	node(ll l,ll r=0,ll v=0):l(l),r(r),v(v){}
	bool operator <(const node &a)const{			//让set按左节点左到右排序
		return l<a.l;
	}
};
set<node>s;

mutable 的意思是「可变的」，让我们可以在后面的操作中修改 v 的值．在 C++ 中，mutable 是为了突破 const 的限制而设置的．被 mutable 修饰的变量（mutable 只能用于修饰类中的非静态数据成员），将永远处于可变的状态，即使在一个 const 函数中．

这意味着，我们可以直接修改已经插入 set 的元素的 v 值，而不用将该元素取出后重新加入 set．

拆分

如果要对一段区间进行赋值，那及其有可能需要把一个区间拆开，于是可以定义一个函数，用二分找到这个值处于哪一个迭代器，删除这一个迭代器，再删除，建立两个新的值，就相当于拆分。

auto split(int pos){
    auto it=s.lower_bound(node(pos));
    if(it!=s.end()&&it->l==pos)return it;
    it--;
    int L=it->l,R=it->r;
    long long V=it->v;
    s.erase(it);
    s.insert(node(L,pos-1,V));
    return s.insert(node(pos,R,V)).first;
}

修改

在set中删除其中所有被 $l,r$ 覆盖的区域，再新建一个新的节点，即完成。

void assign(ll l,ll r,ll x){
    auto itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
    s.insert(node(l,r,x));
}

修改

同理，找到其中左节点和右节点，依次遍历其中的所有结点，给每一个的值都与 $x$ 进行操作。

其中有一个点需要注意，它需要遍历每个结点的 $v$ ，并把它们加上 $x$ ，如果前面结构体没有 mutable ，这里就会报一个error: cannot assign to return value because function 'operator->' returns a const value。

void add(ll l,ll,r,ll x){
    auto itr=split(r+1),itl=split(l);
    for(auto it=itl;it!=itr;it++){
        it->v+=x;
    }
}
void change(ll l,ll,r,ll x){
    auto itr=split(r+1),itl=split(l);
    for(auto it=itl;it!=itr;it++){
        it->v=x;
    }
}