[數據結構]ODT(珂朵莉樹)實現及其應用，帶圖

本文只發佈於部落格園,其他地方若出現本文均是盜版

演算法引入

需要一種這樣的數據結構,需要支援區間的修改,區間不同值的分別操作。

一般的，我們會想到用線段樹或者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

Split實現

首先我們需要找到x點的位置。這裡我們使用的是set的upper_bound函數,利用這個函數我們可以輕鬆的找到第一個開頭大於x的區間,而x就在這個區間的前一個區間裡面。

當然如果前一個區間開頭剛好是x,那就可以直接返回這個區間節點對應的迭代器。

如果區間開頭不是x,那就說明x在這個區間裡面,我們要做的就是把這個區間分裂開。
首先我們記錄我們要分裂的這個區間的左右端點，以及數值。
然後我們就可以把要分裂的這個區間節點從set里刪除了。
再插入兩個新節點(一個是 “L->(x-1)” 另一個是 “x->R”)。
直接返回x開頭的那個元素的迭代器就好了

flowchart TB
A[“L->R”]–>B[“L->(x-1)”]
A[“L->R”]–>C[“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的作用就是區間賦值。既然我們需要進行區間賦值，那麼我們就要把這個區間整出來。我們把區間的左右端點分割開了

如果從區間上看就是這樣

graph LR
A[“…”]–>B[“L-…”].->C[“…”].->D[“…-(R-1)”]–>E[“R-….”]–>F[“…”]

這時候我們只需要把[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];
    }
}

Tags: 程式碼共享數據結構演算法演算法教程