UOJ Logo negiizhao的博客

博客

关于持久化平衡树

2017-08-27 23:04:30 By negiizhao

OI中对pointer machine常用的持久化方法称为path copying,这种方法需要复制所有发生改变的结点。复制结点会导致地址发生变化,于是也需要复制指向这个结点的结点,这样就能保证不会影响以前的版本。

曾经做过一次调查『您认为什么样的数据结构不能高效地可持久化?』,96人中有47人——即一半人选择了『使用了旋转』。事实上,path copying与是否旋转、是否完全自顶向下都是无关的,只要保证发生改变的结点都被复制了即可。

很多人用merge/split写insert/erase,但这其实是函数式的写法,常数要大一些。函数式并不等于持久化。

我在洛谷P3835进行了一些测试,目前最好的是直接使用path copying的Treap,运行时间1300~1400ms,可见是十分高效的。然而大概还是跑不过RBT

下面是参考代码。

#include <cstdio>
#include <algorithm>

using namespace std;

typedef unsigned int uint;

inline uint rand32()
{
    static uint seed(19260817);
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed;
}

const int _I_Buffer_Size(1 << 24);
char _I_Buffer[_I_Buffer_Size];
char* _I_pos = _I_Buffer;

const int _O_Buffer_Size(1 << 24);
char _O_Buffer[_O_Buffer_Size];
char* _O_pos = _O_Buffer;

inline bool is_digit(const char ch)
{
    return '0' <= ch && ch <= '9';
}

inline int getop()
{
    static char ch;
    while (ch = *_I_pos++, !is_digit(ch))
        ;
    return ch & 15;
}

inline int getint()
{
    int res(0);
    static char ch;
    bool neg(false);
    while (ch = *_I_pos++, !is_digit(ch))
        neg = ch == '-';
    do
        (res *= 10) += ch & 15;
    while (ch = *_I_pos++, is_digit(ch));
    return neg ? -res : res;
}

inline void putint(int n)
{
    char _buf[10];
    char* _pos(_buf);
    if (n < 0)
        *_O_pos++ = '-', n = -n;
    do
        *_pos++ = '0' | n % 10;
    while (n /= 10);
    while (_pos != _buf)
        *_O_pos++ = *--_pos;
}

const size_t _M_Size((1 << 29) - (1 << 26));
char _M[_M_Size];
char* _M_pos(_M + _M_Size);

void* operator new(size_t size)
{
    return _M_pos -= size;
}

void operator delete(void* ptr)
{
}

struct Treap
{
    int value, p, cnt, size;
    Treap* ch[2];

    Treap() : value(0), p(1 << 31), cnt(0), size(0)
    {
        ch[0] = ch[1] = this;
    }
    Treap(int v);
};

Treap* Null(new Treap);

inline Treap::Treap(const int v) : value(v), p(rand32()), cnt(1), size(1)
{
    ch[0] = ch[1] = Null;
}

void pushup(Treap*& o)
{
    o->size = o->ch[0]->size + o->ch[1]->size + o->cnt;
}

void copy(Treap*& o)
{
    o = new Treap(*o);
}

void rotate(Treap*& o, const bool d)
{
    Treap* c(o->ch[!d]);
    o->ch[!d] = c->ch[d];
    c->ch[d] = o;
    pushup(o), pushup(c);
    o = c;
}

void insert(Treap*& o, const int v)
{
    if (o == Null)
    {
        o = new Treap(v);
        return;
    }
    copy(o);
    if (o->value == v)
    {
        ++(o->cnt);
        ++(o->size);
        return;
    }
    bool d(o->value < v);
    insert(o->ch[d], v);
    pushup(o);
    if (o->ch[d]->p > o->p)
        rotate(o, !d);
}

Treap* merge(Treap* o[2])
{
    if (o[0] == Null)
        return o[1];
    if (o[1] == Null)
        return o[0];
    bool d(o[0]->p < o[1]->p);
    Treap* new_o(new Treap(*o[d]));
    o[d] = new_o->ch[!d];
    new_o->ch[!d] = merge(o);
    pushup(new_o);
    return new_o;
}

void erase(Treap*& o, const int v)
{
    if (o == Null)
        return;
    copy(o);
    if (o->value == v)
    {
        --(o->cnt);
        --(o->size);
        if (o->cnt == 0)
        {
            Treap* c[2] = {o->ch[0], o->ch[1]};
            o = merge(c);
        }
        return;
    }
    erase(o->ch[o->value < v], v);
    pushup(o);
}

int rank(Treap*& o, const int v)
{
    if (v == o->value || o == Null)
        return o->ch[0]->size + 1;
    return o->value < v ? o->ch[0]->size + o->cnt + rank(o->ch[1], v) : rank(o->ch[0], v);
}

int select(Treap*& o, const int k)
{
    if (o->ch[0]->size < k && k <= o->ch[0]->size + o->cnt)
        return o->value;
    return o->ch[0]->size < k ? select(o->ch[1], k - o->ch[0]->size - o->cnt) : select(o->ch[0], k);
}

int precursor(Treap*& o, const int v)
{
    if (o == Null)
        return -2147483647;
    return o->value < v ? max(o->value, precursor(o->ch[1], v)) : precursor(o->ch[0], v);
}

int successor(Treap*& o, const int v)
{
    if (o == Null)
        return 2147483647;
    return o->value > v ? min(o->value, successor(o->ch[0], v)) : successor(o->ch[1], v);
}

void debug(Treap*& o, const bool isr = true)
{
    if (o == Null)
        return;
    debug(o->ch[0], false);
    for (int i(0); i != o->cnt; ++i)
        fprintf(stderr, "%d ", o->value);
    debug(o->ch[1], false);
    if (isr)
        fputs("\n", stderr);
}

int N, now;

int main(int argc, char** argv)
{
    fread(_I_Buffer, 1, _I_Buffer_Size, stdin);

    N = getint();

    Treap* Root[500005] = {Null};

    while (N--)
    {
        Root[++now] = Root[getint()];
        switch (getop())
        {
            case 1:
                insert(Root[now], getint());
                break;

            case 2:
                erase(Root[now], getint());
                break;

            case 3:
                putint(rank(Root[now], getint())), *_O_pos++ = '\n';
                break;

            case 4:
                putint(select(Root[now], getint())), *_O_pos++ = '\n';
                break;

            case 5:
                putint(precursor(Root[now], getint())), *_O_pos++ = '\n';
                break;

            case 6:
                putint(successor(Root[now], getint())), *_O_pos++ = '\n';
                break;

            case 7:
                debug(Root[now]);
        }
    }

    fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout);

    return 0;
}

评论

Tmp1
这个可以持久化完全是因为Treap本身的性质,与旋转无关吧
OldDriverTree
牛逼啊 平衡树大师!

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。