title: Rank the suffixes of a list
body: <p><strong>ranking</strong> an element <code>x</code> in an array/list is just to find out how many elements in the array/list that strictly smaller than x.</p>
  
  <p>So ranking a list is just get ranks of all elements in the list.</p>
  
  <p>For example, <code>rank [51, 38, 29, 51, 63, 38] = [3, 1, 0, 3, 5, 1]</code>, i.e., there are 3 elements smaller than 51, etc.</p>
  
  <p>Ranking a list can be done in O(NlogN). Basically, we can sort the list while remembering the original index of each element, and then see for each element, how many before it.</p>
  
  <hr>
  
  <p>The question here is <strong>How to rank the suffixes of a list, in <code>O(NlogN)</code></strong>?</p>
  
  <p>Ranking the suffixes of a list means:</p>
  
  <p>for list [3; 1; 2], rank [[3;1;2]; [1;2]; [2]]</p>
  
  <p>note that elements may not be distinct.</p>
  
  <hr>
  
  <p><strong>edit</strong></p>
  
  <p>We don't need to print out all elements for all suffixes. You can image that we just need to print out a list/array, where each element is a rank of a suffix.</p>
  
  <p>For example, rank suffix_of_[3;1;2] = rank [[3;1;2]; [1;2]; [2]] = [2;0;1] and you just print out [2;0;1].</p>
  
  <hr>
  
  <p><strong>edit 2</strong></p>
  
  <p>Let me explain what is <em>all suffixes</em> and what means <em>sorting/ranking all suffixes</em> more clearly here.</p>
  
  <p>Suppose we have an array/list [e1;e2;e3;e4;e5].</p>
  
  <p>Then all suffixes of [e1;e2;e3;e4;e5] are:</p>
  
  <p>[e1;e2;e3;e4;e5]<br>
  [e2;e3;e4;e5]<br>
  [e3;e4;e5]<br>
  [e4;e5]<br>
  [e5]  </p>
  
  <p>for example, all suffixes of [4;2;3;1;0] are</p>
  
  <p>[4;2;3;1;0]<br>
  [2;3;1;0]<br>
  [3;1;0]<br>
  [1;0]<br>
  [0]  </p>
  
  <p>Sorting above 5 suffixes implies lexicographic sort. sorting above all suffixes, you get</p>
  
  <p>[0]<br>
  [1;0]<br>
  [2;3;1;0]<br>
  [3;1;0]<br>
  [4;2;3;1;0]  </p>
  
  <p>by the way, if you can't image how 5 lists/arrays can be sorted among them, just think of sorting strings in lexicographic order.</p>
  
  <p>"0" &lt; "10" &lt; "2310" &lt; "310" &lt; "42310"</p>
  
  <hr>
  
  <p>It seems sorting all suffixes is actually sorting all elements of the original array. </p>
  
  <p>However, please be careful that all elements may not be distinct, for example</p>
  
  <p>for [4;2;2;1;0], all suffixes are:</p>
  
  <p>[4;2;2;1;0]<br>
  [2;2;1;0]<br>
  [2;1;0]<br>
  [1;0]<br>
  [0]  </p>
  
  <p>then the order is</p>
  
  <p>[0]<br>
  [1;0]<br>
  [2;1;0]<br>
  [2;2;1;0]<br>
  [4;2;2;1;0]  </p>