ODT简介

ODT(old driver tree 老驱动树)又名珂朵莉树是由codeforcescodeforcescodeforces上一位叫做ODTODTODT的用户提出的一种基于平衡树的暴力数据结构。

这个数据结构的玄妙之处在于它并没有稳定的时间复杂度，因此只有在数据随机/水的情况下才会有较好的表现。

实现前提&&实现原理

前提是必须要有区间覆盖操作且数据较随机/水

实现原理：将元素相同的区间推平一起处理，即如果区间[l,r][l,r][l,r]中的所有数[al,al+1...ar][a_l,a_{l+1}...a_r][al,al+1...ar]全部相同的话就将这个区间的信息用一个节点表示。

从上述描述可以看出这个数据结构是非常暴力玄学的

初始化

然后对于每段区间我们可以用一个三元组[l,r,v][l,r,v][l,r,v]来表示它的左/右端点和整个区间的值，然后对于这些区间的信息可以用一个setsetset来维护。

下面是ODTODTODT节点的初始化代码：

struct Node{
	int l,r;
	mutable int v;
	Node(int l,int r=-1,int v=0):l(l),r(r),v(v){}
	friend inline bool operator<(const Node&a,const Node&b){
		return a.l<b.l;
	}
};
set<Node>S;
typedef set<Node>::iterator It;

然后我们要谈谈ODTODTODT两个重要的操作splitsplitsplit和assignassignassign

split操作

ODTODTODT的splitsplitsplit函数split(pos)split(pos)split(pos)表示把pospospos所在的这个区间[l,r,v][l,r,v][l,r,v]分成[l,pos−1,v][l,pos-1,v][l,pos−1,v]和[pos,r,v][pos,r,v][pos,r,v]并且返回后者的迭代器。

实现很简单直接lowerboundlower_boundlowerbound出pospospos所在的区间然后加几个小特判。

代码：

inline It split(int pos){
	It it=S.lower_bound(pos);
	if(it!=S.end()&&it->l==pos)return it;
	--it;
	if(pos>it->r)return S.end();
	int l=it->l,r=it->r,v=it->v;
	S.erase(it);
	S.insert(Node(l,pos-1,v));
	return S.insert(Node(pos,r,v)).first;
}

assign操作

ODTODTODT最核心的操作assignassignassign，assign(l,r,v)assign(l,r,v)assign(l,r,v)表示把区间[l,r][l,r][l,r]全部赋值为vvv并且会将这r−l+1r-l+1r−l+1个点合并成一个ODTODTODT节点插入到ODTODTODT中，由于数据随机的时候ODTODTODT中节点会快速减少，因此ODTODTODT复杂度此时十分接近O(nlogn)O(nlog_n)O(nlogn)

具体实现可以通过上面提到的splitsplitsplit函数。

代码：

inline void assign(int l,int r,int v){
	It R=split(r+1),L=split(l);
	S.erase(L,R),S.insert(Node(l,r,v));
}

其它操作

至此，与ODTODTODT相关的操作已经基本讲完了。

剩下的操作与ODTODTODT本身关系并不大，相当于就是遍历每一个ODTODTODT节点暴力进行修改和查询。

区间第k小

代码：

typedef set<Node>iterator It;
typedef pair<long long,int> pli;
vector<pli>q;
inline int rank(int l,int r,int kth){
    It R=split(r+1),L=split(l);
    q.clear();
    for(It it=L;it!=R;++it)q.push_back(pli(it->v,it->r-it->l+1));
    sort(q.begin(),q.end());
    for(ri i=0;i<q.size();++i){
        kth-=q[i].second;
        if(kth<=0)return q[i].first;
    }
    return -1;
}

区间加

代码：

inline void add(int l,int r,int v){
    It L=split(l),R=split(r+1);
    for(It it=L;it!=R;++it)(it->v)+=v;
}

区间所有数的k次方和

代码：

typedef long long ll;
inline ll query(int l,int r,int k,ll mod){
    ll ret=0;
    It L=split(l),R=split(r+1);
    for(It it=L;it!=R;++it)ret=(ret+(ll)(it->r-it->l+1)*ksm(it->v,k,mod)%mod)%mod;
    return ret;
}

几道水题

codeforces896Ccodeforces896Ccodeforces896C

codeforces915Ecodeforces915Ecodeforces915E

codeforces343Dcodeforces343Dcodeforces343D

bzoj4592bzoj4592bzoj4592

洛谷2787洛谷2787洛谷2787

巴特西

ODT(old driver tree)详解（带例题）

文章目录