Conversion between Factorial Numbers and Permutations

Conversion methods can be found in http://en.wikipedia.org/wiki/Factorial_number_system A naive algorithm takes \[O(n^2)\], which can be reduced to \[O(nlogn)\] if segment trees are used. Converting a factorial number to a permutation Suppose the length of the factorial number is n. Let Perm be the smallest standard permutation of length n(a.k.a all values are distinct and are from 0 to n-1) Let t[o..n-1] be an array of integers. Initially set t[i]=1 for all \[ 0 \leq i <n\] Let sum[i..j] be the sum of t[i..j]. The crucial part of the original algorithm is to find k-th(zero-based) unused number in Permu, which can be done as follows: Searching for sum[0..j] with smallest j such that sum[0..j]=k+1, after finding the deserved j, set t[j]=0 and update sum array. updating can be done in O(logn) with the help of a segment tree, and modified binary search in the segment tree takes O(logn)

// O(nlogn)
vector<int> fac_to_permu(vector<int> &fac){
  int n=fac.size();
  SegmentTree<int,int> st;
  vector<int> data(n,1);
  st.build_tree(data);
  vector<int> permu(n,0);
  for(int i=0;i<n;i++){
    permu[i]=st.find_idx(fac[n-i-1]+1);
    st.update(permu[i],0);
  }
  return permu;
}

(You can find st.find_idx() in the implementation of segment tree below) Converting a permutation to a factorial number Let p be the permutation. Let l be an empty list. First we scan the permutation backwardly. For each index i, the corresponding factorial digit is the index of p[i] in l (zero-based) after inserting p[i] into a proper place of l such that l is sorted. Again, a naive algorithm takes \[O(n^2)\]. Let t[o..n-1] be an array of integers. Initially set t[i]=0 for all \[ 0 \leq i <n\] Let sum[i..j] be the sum of t[i..j]. For each index i, set t[p[i]]=1, which imples that p[i] has been inserted into a proper place of l, the corresponding factorial digit=sum[0..p[i]] (sum[0..p[i]] basically counts how many numbers there are before p[i] in the sorted list l). With the help of a segment tree, updating t[p[i]]=1 and finding sum[0..p[i]] take O(logn).

// O(nlogn)
vector<int> permu_to_fac(vector<int> &permu){
  int n=permu.size();
  SegmentTree<int,int> st;
  vector<int> fac(n,0),data(n,0);
  st.build_tree(data);
  for(int i=n-1;i>=0;i--){
    fac[n-i-1]=st.query(0,permu[i]);
    st.update(permu[i],1);
  }
  return fac;
}

Segment Tree

template <class Dtype,class Qtype>
class SegmentTree{
private:
  // st size>=2*2^(floor(log2(n))+1) or loosely 4*n
  // default implementation: sum of range[L..R]
  // Dtype: data type
  // Qtype: query type
  Qtype st[800001];
  int n;
  int left(int p){return p<<1;}
  int right(int p){return (p<<1)+1;};
  void build(int p,int L,int R,Dtype data[]){
    if(L==R){
      st[p]=data[L];
    }
    else{
      build(left(p),L,(L+R)/2,data);
      build(right(p),(L+R)/2+1,R,data);
      Qtype l=st[left(p)];
      Qtype r=st[right(p)];
      st[p]=l+r;
    }
  }
  void build(int p,int L,int R,vector<Dtype> &data){
    if(L==R){
      st[p]=data[L];
    }
    else{
      build(left(p),L,(L+R)/2,data);
      build(right(p),(L+R)/2+1,R,data);
      Qtype l=st[left(p)];
      Qtype r=st[right(p)];
      st[p]=l+r;
    }
  }
  bool check(int L,int R,int i,int j){
    return !(i>R||j<L);
  }
  Qtype rmq(int p,int L,int R,int i,int j){
    if(i<=L&&R<=j){
      return st[p];
    }
    bool chk_left=check(L,(L+R)/2,i,j);
    bool chk_right=check((L+R)/2+1,R,i,j);
    if(chk_left&&chk_right){
      return rmq(left(p),L,(L+R)/2,i,j)+rmq(right(p),(L+R)/2+1,R,i,j);
    }
    else if(chk_left){
      return rmq(left(p),L,(L+R)/2,i,j);
    }
    else if(chk_right){
      return rmq(right(p),(L+R)/2+1,R,i,j);
    }
  }
  void _update(int pos,Dtype value,int p,int L,int R){
    if(L==R){
      st[p]=value;
    }
    else{
      int m=(L+R)/2;
      if(pos<=m){
    _update(pos,value,left(p),L,(L+R)/2);
      }
      else{
    _update(pos,value,right(p),(L+R)/2+1,R);
      }
      Qtype l=st[left(p)];
      Qtype r=st[right(p)];
      st[p]=l+r;
    }
  }
  // Extra Functions for the default implementation
  // Warning: For the default implementation only!
  // Binary search for an index where st[index]==targetValue
  // Returns left-most index if multiple valid indices exist
  int _find_idx(Qtype targetValue,int p,int L,int R){
    if(L==R){
      if(st[p]==targetValue){
    return L;
      }
      else{
    return -1;
      }
    }
    if(st[left(p)]>=targetValue){
      return _find_idx(targetValue,left(p),L,(L+R)/2);
    }
    else{
      return _find_idx(targetValue-st[left(p)],right(p),(L+R)/2+1,R);
    }
  }
public:
  void build_tree(int n,Dtype data[]){
    this->n=n;
    build(1,0,n-1,data);
  }
  void build_tree(vector<Dtype> &data){
    this->n=data.size();
    build(1,0,n-1,data);
  }
  Qtype query(int left,int right){
    return rmq(1,0,n-1,left,right);
  }
  void update(int pos,Dtype value){
    _update(pos,value,1,0,n-1);
  }
  // Extra Functions for default implementation
  int find_idx(Qtype targetValue){
    return _find_idx(targetValue,1,0,n-1);
  }
};