Splay Tree

/*
 * Splay Tree
 * Implicit order, can be ordered
 * based on explicit key
 */

struct Node; Node * nil, * root;
struct Node{
    Node * child[2], * parent;
    long value, size;
    long sum,lazy;
    Node( long value = 0 ):value( value ),size( 1 ),sum( value ),lazy( 0 ){
        child[0] = child[1] = parent = nil;
   }
};
void initTree( void ){
    nil = new Node( -1 );
    nil->child[0] = nil->child[1] = nil->parent = nil;
    nil->value = nil->size = nil->sum = 0;
    root = nil;
}
void pushDown( Node * x ){ /* is necessary if there is any lazy propagation */
    if( x != nil and x->lazy ){
        x->child[0]->lazy += x->lazy; x->child[1]->lazy += x->lazy;
        x->value += x->lazy; x->lazy = 0;
    }
}
long getSum( Node *x ){ /* is called by only update function */
    return ( x == nil ) ? 0 : ( x->sum + x->lazy*x->size );
}
void update( Node * x ){
    if( x == nil ) return;
    pushDown( x );
    x->size = x->child[0]->size + x->child[1]->size + 1;
    x->sum = getSum( x->child[0] ) + getSum( x->child[1] ) + x->value;
}
void setLink( Node * x, Node * y, long d ){
    x->child[d] = y; y->parent = x;
}
long getDir( Node * x, Node * y ){
    return x->child[0] == y ? 0 : 1;
}
void rotate( Node * x, long d ){
    Node * y = x->child[d], * z = x->parent;
    pushDown( z ); pushDown( x ); pushDown( y );
    setLink( x, y->child[d ^ 1], d );
    setLink( y, x, d ^ 1 );
    setLink( z, y, getDir( z, x ) );
    update( x ); update( y ); update( z );
}
void splay( Node * x ){
    while( x->parent != nil ){
        Node * y = x->parent, * z = y->parent;
        long dy = getDir( y, x ), dz = getDir( z, y );
        if( z == nil ) rotate( y, dy );
        else if( dy == dz ) rotate( z, dz ), rotate( y, dy );
        else rotate( y, dy ), rotate( z, dz );
    }
}
Node * nodeAt( Node * x, long pos ){
    while( pushDown( x ), x->child[0]->size+1 != pos ){
        if( pos <= x->child[0]->size ) x = x->child[0];
        else pos -= x->child[0]->size + 1, x = x->child[1];
    } return splay( x ), x;
}