Splay Tree 소스 코드

주: 이 코드 는 본인 이 쓴 것 이 아니 라 실현 방식 은 아래 에서 위로, ACM 문 제 를 풀 때 교과서 의 위 에서 아래로 데이터 처리 보다 좋 습 니 다.
개인 은 현재 지침 을 비교적 좋아 하기 때문에 인터넷 에서 지침 이 실현 되 는 소스 코드 를 찾 았 고 개인 적 인 이해 주석 과 다른 조작 만 추가 했다.
http://dongxicheng.org/structure/splay-tree/이 블 로 그 는 Splay Tree 에 대한 분석 이 비교적 투철 하 다. 주의해 야 할 것 은 Splay Tree 의 회전 조작 은 다른 균형 트 리, 예 를 들 어 Red Black Tree 의 조작 과 코드 가 다 르 기 때문에 구체 적 으로 그림 을 그 릴 수 있다 는 것 이다.
Splay Tree 의 Splay 함수 와 구간 조작 방법 을 이 해 했 고 기본적으로 Splay Tree 를 파악 했다.

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int const maxn=300000;

#define bint __int64
struct node
{
    int value,size;
    int add;
    bint sum;
    node *ch[2], *pre;
}tree[maxn],*Null, *root;//    Null       

int num[maxn];
int n,m;

int top=0;
node *New_Node(int x)
{
    node *p=&tree[top++];
    p->ch[0]=p->ch[1]=p->pre=Null;
    p->add=0;
    p->sum=x;
    p->size=1;
    p->value=x;
    return p;
}

void Push_Down(node *x)
{
    if (x == Null) return;
    x->value+=x->add;
    x->ch[0]->add+=x->add;
    x->ch[1]->add+=x->add;
    if(x->ch[0]!=Null)
        x->ch[0]->sum+=(bint)(x->add)*(x->ch[0]->size);
    if(x->ch[1]!=Null)
        x->ch[1]->sum+=(bint)(x->add)*(x->ch[1]->size);
    x->add=0;
}

void Update(node *x)
{
    if (x == Null) return;
    x->size = x->ch[0]->size + x->ch[1]->size + 1;
    x->sum = (bint)x->value+ x->ch[0]->sum + x->ch[1]->sum;
}

//      redblack  ，    x   
void Rotate(node *x, int c)//c=0: left rotate c=1: right rotate
{
    node *y = x->pre;
    Push_Down(y);
    Push_Down(x);
    y->ch[! c] = x->ch[c];
    x->pre = y->pre;
    if (x->ch[c] != Null)
        x->ch[c]->pre = y;
    if (y->pre != Null)
        y->pre->ch[y->pre->ch[1] == y] = x;//    y->pre       y
    y->pre = x;
    x->ch[c] = y;
    if (y == root) root = x;
    Update(y);
}

//   x    f   
void Splay(node *x, node *f)
{
    Push_Down(x);
    while(x->pre != f)
    {
        if (x->pre->pre == f)
            Rotate(x, x->pre->ch[0] == x);
        else
        {
            node *y = x->pre, *z = y->pre;
            if (z->ch[0] == y)//left
                if (y->ch[0] == x) //LL
                    Rotate(y, 1), Rotate(x, 1);
                else
                    Rotate(x, 0), Rotate(x, 1);//LR
            else//right
                if (y->ch[1] == x) //RR
                    Rotate(y, 0), Rotate(x, 0);
                else
                    Rotate(x, 1), Rotate(x, 0);//RL
        }
    }
    Update(x);
}

//         K   ，        f   
void Select(int k, node *f)
{
    node *now=root;
    while(true)
    {
        Push_Down(now);
        int tmp = now->ch[0]->size;
        if (tmp + 1 == k) break;
        if (k <= tmp)
            now = now->ch[0];
        else
            now = now->ch[1], k -= tmp + 1;
    }
    //printf("Select: %d
",now->value);
    Splay(now, f);
}

node *Make_Tree(int l, int r, node *fa)
{
    if (l > r) return Null;
    int mid = (l + r) >> 1;
    node *p = New_Node(num[mid]);
    p->ch[0] = Make_Tree(l, mid-1, p);
    p->ch[1] = Make_Tree(mid+1, r, p);
    p->pre = fa;
    Update(p);
    return p;
}

void remove(int left,int right){//    [left,right]
    Select(left,Null);
    Select(right+2,root);
    root->ch[1]->ch[0] = Null;
    Splay(root->ch[1],Null);
}

void ADD(int left,int right,int cnt){
    Select(left,Null);
    Select(right+2,root);
    root->ch[1]->ch[0]->add += cnt;
    root->ch[1]->ch[0]->sum+=(bint)cnt*(root->ch[1]->ch[0]->size);
    Splay(root->ch[1]->ch[0],Null);
}

node *makeTree(int l, int r, int value, node *fa)
{
    if (l > r) return Null;
    int mid = (l + r) >> 1;
    node *p = New_Node(value);
    p->ch[0] = makeTree(l, mid-1,value, p);
    p->ch[1] = makeTree(mid+1, r,value, p);
    p->pre = fa;
    Update(p);
    return p;
}

void insert(int pos,int cnt,int value){// pos        cnt   value  
    Select(pos+1,Null);
    Select(pos+2,root);
    root->ch[1]->ch[0] = makeTree(1,cnt,value,root->ch[1]);
    Splay(root->ch[1]->ch[0],Null);
}

void print(node *root){
    node *p = root;
    if(p!=Null){
        if(p->ch[0]!=Null)print(p->ch[0]);
        printf("%d,parent=%d,size=%d
",p->value,p->pre->value,p->pre->size);
        if(p->ch[1]!=Null) print(p->ch[1]);
    }
}

int main()
{
    top=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
    }

    Null=New_Node(0);
    Null->size=0;

    //head
    root=New_Node(-1);
    //tail
    root->ch[1]=New_Node(-1);
    root->ch[1]->pre=root;
    Update(root);

    //root->ch[1] is the really root
    root->ch[1]->ch[0]=Make_Tree(1,n,root->ch[1]);
    Update(root->ch[1]);
    Update(root);
    //print(root);
    char s[2];
    for(int i=0;i<m;i++)
    {

        scanf("%s",s);
        if(s[0]=='C')
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            ADD(a,b,c);
          //  Select(a,Null);
           // print(root);
         //   Select(b+2,root);
           // cout<<"=================================="<<endl;
           // print(root);
            //root->ch[1]->ch[0]->add+=c;
            //root->ch[1]->ch[0]->sum+=(bint)c*(root->ch[1]->ch[0]->size);
        }
        else
        {
            int a,b;
            scanf("%d%d",&a,&b);
            //   a-1      Null ，   b+1      root 
            //（ root    ），    （root       [a,b]）
            Select(a,Null);//  root size 1，     a-1+1=a,a-1   root 
            //print(root);
            Select(b+2,root);//     b+1+1=b+2，a-1    
           // cout<<"=================================="<<endl;
           // print(root);
            printf("%I64d
",root->ch[1]->ch[0]->sum);
        }
    }
    return 0;
}