Order Statistic Tree — Rank + Select in O(log N)

class Node { int val; int size; Node left, right; }
int sizeOf(Node n) { return n == null ? 0 : n.size; }

Node select(Node n, int k) {
  int leftSize = sizeOf(n.left);
  if (k == leftSize + 1) return n;
  return k <= leftSize ? select(n.left, k) : select(n.right, k - leftSize - 1);
}

int rank(Node n, int val) {
  if (n == null) return 0;
  if (val < n.val) return rank(n.left, val);
  if (val > n.val) return sizeOf(n.left) + 1 + rank(n.right, val);
  return sizeOf(n.left) + 1;
}