数据结构树的运用（数据结构ODT珂朵莉树）
数据结构树的运用（数据结构ODT珂朵莉树）含义inline bool operator<(const Odt_Node &a const Odt_Node &b) { return a.l < b.l; }基本操作操作名ODT基本节点可以由各种数据结构进行维护，一般我们使用C 自带的数据结构std::set。按节点的左端点进行升序排序。这样我们就可以完整的保存一个1~n的序列信息了。C 代码如下
需要一种这样的数据结构 需要支持区间的修改 区间不同值的分别操作。
一般的，我们会想到用线段树或者Splay等支持序列操作的数据结构。但是我们这里讲引入一种更加简单的数据结构。
算法介绍节点信息节点定义ODT的基本节点将保存如下信息。
- 该节点所代表序列的左右区间
- 该节点所代码的区间的值C 代码如下struct Odt_Node { int l r; int val; };
可以发现一个ODT节点需要代表的是一块值全部相同的区间
节点信息维护ODT基本节点可以由各种数据结构进行维护，一般我们使用C 自带的数据结构std::set。
按节点的左端点进行升序排序。这样我们就可以完整的保存一个1~n的序列信息了。
C 代码如下
inline bool operator<(const Odt_Node &a const Odt_Node &b)
{
return a.l < b.l;
}基本操作
|
操作名 |
含义 |
|
split(x) |
把ODT节点(区间)单独分开，使得有一个子节点(区间)的左端点为x。(在x之前把区间分裂开) |
|
assign(l r val) |
把区间[l r]全部赋值为val |
首先我们需要找到x点的位置。这里我们使用的是set的upper_bound函数 利用这个函数我们可以轻松的找到第一个开头大于x的区间 而x就在这个区间的前一个区间里面。
当然如果前一个区间开头刚好是x 那就可以直接返回这个区间节点对应的迭代器。
- 如果区间开头不是x 那就说明x在这个区间里面 我们要做的就是把这个区间分裂开。
- 首先我们记录我们要分裂的这个区间的左右端点，以及数值。
- 然后我们就可以把要分裂的这个区间节点从set里删除了。
- 再插入两个新节点(一个是 "L->(x-1)" 另一个是 "x->R")。
- 直接返回x开头的那个元素的迭代器就好了
L->R
L->(x-1)
x->R
差不多就上面这个样子。
代码如下
inline auto split(int x)
{
if (x > n)
return S.end();
auto iter = --S.upper_bound({x 0 0});
if (iter->l == x)
return iter;
int l = iter->l r = iter->r;
char v = iter->v;
S.erase(iter);
S.insert({l x - 1 v});
return S.insert({x r v}).first;
}Assign实现
Assign的作用就是区间赋值。既然我们需要进行区间赋值，那么我们就要把这个区间整出来。我们把区间的左右端点分割开了
如果从区间上看就是这样
...
L-...
...
...-(R-1)
R-....
...
这时候我们只需要把[L R)之间的节点删除就好了。
然后插入一个新的直接[L R)的区间节点。
有点像是把这些零零碎碎的节点直接推平重整
代码如下
inline void assign(int l int r char v)
{
auto itr = split(r 1) itl = split(l);
S.erase(itl itr);
S.insert({l r v});
}特殊操作排序算法
有时候我们不仅仅需要满足区间修改这个操作。我们可能还需要进行区间排序。
怎么实现呢？我们当然不可能在ODT里跑一个数组里的那样的排序算法，难写，而且浪费时间
我们考虑到排序操作的影响结果——就是把第几小的放到前面。
这和ODT的区间修改不谋而合。我们只需要统计出各个数的数量，然后从小到大依次修改对应的区间就好了。
至于统计出现数的数量，你可以使用桶排序(数组或者map都行)。
一般题目也是要求给一个字符串排序。
代码如下
int cnt['Z' 1];
inline void conut(int l int r)
{
memset(cnt 0 sizeof cnt);
auto itr = split(r 1) itl = split(l);
for (auto i = itl; i != itr; i )
{
cnt[i->v] = i->r - i->l 1;
}
}
inline void sort(int l int r)
{
conut(l r);
int nl = l;
for (int i = 'A'; i <= 'Z'; i )
{
assign(nl nl cnt[i] - 1 i);
nl = cnt[i];
}
}
- [数据结构]ODT(珂朵莉树)实现及其应用，带图
- 算法引入
- 算法介绍
- 节点信息
- 节点定义
- 节点信息维护
- 基本操作
- Split实现
- Assign实现
- 特殊操作
- 排序算法
原文：https://www.cnblogs.com/Icys/p/ODT.html
