アルゴリズム導論14(データ構造の拡張)

14.1動的順序統計ツリーは、任意の順序統計量をO時間内に決定することができるように、各ノード上に付加情報を簡単に記憶する赤いツリーにすぎない.

struct node
{
    int key,color,size;
    node *left,*right,*p;
    node():color(BLACK){}
};

//          ，      O(logn)。
node *OSSelect(node *x,int i)
{
    int r=x->left->size+1;
    if(i==r)return x;
    else if(i<r)return OSSelect(x->left,i);
    else return OSSelect(x->right,i-r);
}

//        ，      O(logn)。
int OSRank(node *root,node *x)
{
    int r=x->left->size+1;
    node *y=x;
    while(y!=root)
    {
        if(y==y->p->right)r+=y->p->left->size+1;
        y=y->p;
    }
    return r;
}

//        
//（1）  ：                  x，   x->size  。      size 1。
//（2）  ：            y（            ）       ，           size    。
//（3）             。
y->size=x->size;
x->size=x->left->size+x->right->size+1;

14.2データ構造の拡張方法
14.3区間ツリー区間ツリー(interval tree)は、動態集合を維持する赤黒い木です.

struct node
{
    int key,color;
    node *left,*right,*p;
    pair<int,int> int;
    node():color(BLACK){}
};

//  i j    。
bool overlap(pair<int,int> i,pair<int,int> j)
{
    return i.first<j.second&&j.first<i.second;
}

//            x   ， x->int i  ；       ，   nil。      O(logn)。
node *intervalSearch(node *root,pair<int,int> i)
{
    node *x=root;
    while(x!=nil&&overlap(i,x->int))
    {
        if(x->left!=nil&&x->left->max>=i.first)x=x->left;
        else x=x->right;
    }
    return x;
}

//      
x->max=max(max(x->int.second,x->left->max),x->right->max);