orderset.cpp

struct node{
        int num_active_leaves;
        void split(node& l, node& r){}
        void merge(node& l, node& r){
                num_active_leaves = l.num_active_leaves + r.num_active_leaves;
        }
        bool operator<(const node& n)const{
                return num_active_leaves < n.num_active_leaves;
        }
};
int binary_search(node k)
//search the last place i, such that merge( everyting to the left of i(including i) ) compares less than k
{
        int root = 1;
        node n=identity; //identity satisfies merge(identity,y) = merge(y,identity) = y for all y.
        assert(!(k<identity));
        while(!isleaf(root)){
                int left_child = root<<1, right_child = left_child|1;
                tree[root].split(tree[left_child],tree[right_child]);
                node m;
                m.merge(n,tree[left_child]);
                if(m<k){//go to right side
                        n=m;
                        root=right_child;
                }else root=left_child;
        }
        node m;
        m.merge(n,tree[root]);
        mergeup(root);
        if(m<k)return root-leftmost_leaf;
        else return root-1-leftmost_leaf;
}