@fuheimao 2015-08-21T12:27:06.000000Z 字数 1833 阅读 619

# Treap(可持久化）

Treap 腹黑猫 数据结构

#include "iostream"#include "cstdlib"using namespace std;struct Node{    Node* Child[2];    int Key;    int Priority;    int Size;    void Maintain(){        Size = 1;        if (Child[0] != NULL) Size += Child[0]->Size;        if (Child[1] != NULL) Size += Child[1]->Size;    }};Node* Root = NULL;int Size(Node* A){    return (A == NULL ? 0 : A->Size); }Node* Merge(Node* A, Node* B){    if (A == NULL) return B;    if (B == NULL) return A;    if (A->Priority < B->Priority){        A->Child[1] = Merge(A->Child[1], B);        A->Maintain();        return A;    }else{        B->Child[0] = Merge(A, B->Child[0]);        B->Maintain();        return B;    }}pair<Node*, Node*> Split(Node* A, int K){    if (A == NULL) return pair<Node*, Node*>(NULL, NULL);    pair<Node*, Node*> DoubleRoot;    if (K <= Size(A->Child[0])){        DoubleRoot = Split(A->Child[0], K);        A->Child[0] = DoubleRoot.second;        A->Maintain();        DoubleRoot.second = A;    }else{        DoubleRoot = Split(A->Child[1], K - Size(A->Child[0]) - 1);        A->Child[1] = DoubleRoot.first;        A->Maintain();        DoubleRoot.first = A;    }    return DoubleRoot;}int FindKth(int K){ //第K小     pair<Node*, Node*> Left = Split(Root, K - 1);    pair<Node*, Node*> Right = Split(Left.second, 1);    Node* Kth = Right.first;    Root = Merge(Merge(Left.first, Kth), Right.second);    return Kth->Key;}int Rank(Node* Top, int Key){ //Key为第几大     if (Top == NULL) return 0;    return (Key < Top->Key ? Rank(Top->Child[0], Key) : Rank(Top->Child[1], Key) + Size(Top->Child[0]) + 1);}void Insert(int Key){    Node* NewNode = new Node();    NewNode->Key = Key;    NewNode->Priority = rand();    NewNode->Child[0] = NewNode->Child[1] = NULL;    NewNode->Maintain();    int Pos = Rank(Root, Key);    pair<Node*, Node*> DoubleRoot = Split(Root, Pos);    Root = Merge(Merge(DoubleRoot.first, NewNode), DoubleRoot.second);}void Remove(int Key){    int K = Rank(Root, Key);    pair<Node*, Node*> Left = Split(Root, K - 1);    pair<Node*, Node*> Right = Split(Left.second, 1);    Root = Merge(Left.first, Right.second);}void Modify(int KeyBefore, int KeyAfter){    Remove(KeyBefore);    Insert(KeyAfter);}int main(int argc, char const *argv[]){    Insert(100);    Insert(500);    Insert(300);    Insert(200);    Remove(100);    cout << Rank(Root, 300);    return 0;}

• 私有
• 公开
• 删除