ODT(珂朵莉树)学习笔记

$ODT$是一种~~玄学~~数据结构（?），很多涉及到区间赋值与区间询问的问题都可以用$ODT$水过去 $ODT$基于数据随机，暂时没有严格的复杂度证明，可以在赛场上骗分 $ODT$的基本思想：用$set$维护若干个块，在必要的时候将某个大块分成两个小块，或者将若干个小块整合成一个大块（也许是分块思想？） 分裂(split)操作:将$[l,r]$区间进行分裂，分成$[l,k-1]$和$[k,r]$两个区间。 代码: ``` struct Node{ int l,r; mutable int val; bool operator<(const Node &rhs)const { return l<rhs.l; } }; #define reg register #define It set<Node>::iterator It split(reg int pos){ It iter=st.lower_bound((Node){pos,0,0}); if(iter!=st.end() && iter->l==pos)return iter; iter--; int l=iter->l,r=iter->r,val=iter->val; st.erase(iter); st.insert((Node){l,pos-1,val}); return st.insert((Node){pos,r,val}).first; } ``` 这里有几个冷知识： - mutable:可以强行突破const带来的影响，我们知道，迭代器访问的是结构体的*this ，这个this是一个const类型的，如果不打破const的限制，我们后面的修改操作就难以进行。 - st.insert(...).first: set::insert操作返回一个pair类型的数据，first返回的是插入之后数据的迭代器,second返回的是插入是否成功，成功返回true，不成功返回false 这段代码的作用是将$pos$所在的块$[l,r](l\le pos \le r)$进行分裂成$[l,pos-1]$与$[pos,r]$两块，并返回$[pos,r]$那块在set中的迭代器 推平(assign)操作：将$[l,r]$区间所有的值全部重置为$c$，并且将$[l,r]$变成一个块（将其中所有的块全部删掉） 代码 ``` void assign(reg int l,reg int r,reg int val){ It iter2=split(r+1),iter=split(l); st.erase(iter,iter2); st.insert((Node){l,r,val}); } ``` 这段代码非常简单易懂，唯一需要注意的地方就是: ## 一定要先分裂右边那块！ 自己手动模拟一下就可以发现先分裂左边那块带来的影响与我们想要到达的效果是不同的。 其他操作： ``` void XXX(reg int l,reg int r){ for(It iter2=split(r+1),iter=split(l);iter!=iter2;iter++) { ... } } ``` 这一段代码非常暴力，不管什么操作，查询或者修改，只要暴力能做的，就在这里用暴力的方法做，只不过把对象改成每个块而已，因为每个块里面的元素的值是相同的，所以我们尽管放心大胆的修改。 预处理： ``` for(reg int i=1;i<=n;i++) a[i]=read(),st.insert((Node){i,i,a[i]}); ``` 一开始的时候只要给每个元素单独一个块就好了。 $ODT$很好理解，但是也很容易卡 一开始的时候，有$N$个块。如果没有修改操作，全是$1-N$的查询操作，那么每次操作的复杂度就是$O(N)$的，这个复杂度相当于暴力操作，所以$ODT$只适合在数据完全随机的情况下使用，卡掉$ODT$的方法很简单，只需要不布置修改操作，只布置$1-N$的询问，就能让$ODT$做到$O(QN)$的复杂度。 # The end