别急！
大家在评论区可以看到，这道题有一定的难度：不少人给出了错误，或者超时的答案。
尽管最高赞给出的答案的确是正确的，其实有一个简单很多的做法：
对N生成二叉搜索树，然后用M索引之。
等下，这不是O(n log n)的吗？
所以才说别急！我们想一想，当M < N的时候，这个二叉树，并不是所有节点，都会被索引。
那，我们为什么要去把不会被用的二叉树部分构建出来捏？
但是，我们怎么知道‘树的那一部分会被用上’？
答案是，我们可以同时交叉构建树跟索引树的过程 - 默认情况下，树是没构建的。当我们索引没被构建过的树，我们会构建这里的最小一部分，然后保存下结果，再进行构建。
class LazyBST:
def __init__(self, arr):
self.constructed = False
self.arr = arr
self.size = len(arr)
def idx(self, index):
if not self.constructed:
self.constructed = True
self.head = self.arr[0]
self.left = LazyBST([x for x in self.arr[1:] if x <= self.head])
self.right = LazyBST([x for x in self.arr[1:] if x > self.head])
if index < self.left.size:
return self.left.idx(index)
elif index == self.left.size:
return self.head
else:
return self.right.idx(index - self.left.size - 1)
有了这个数据结构以后，我们只需要用N构造一下，然后遍历M索引N，就可以了！
B = LazyBST(N)
print([B.idx(m) for m in M])
而这时候，我们整个算法是符合O(n log m)的性能需求的！
以下是证明：
这棵树有log n层，而我们每次对这棵树索引，至多对每层新增一个被构建节点。换句话说，这棵树的每层最多有m个节点。
这时候，每层L的节点平均大小是n / 2^L，于是工作是min(n, m * n / 2^L)。之所以有min，是因为每层只是对N这个列表进行简单变换，总体时间是线性的。
于是，所有工作=
$\sum_{L=0}^{log(n)}min(n, m * \frac{n}{2^L})$
而当L < log(m)时， n < $m * \frac{n}{2^L}$，否则>=，于是工作=
$\sum_{L=0}^{log(m)}n + \sum_{L=log(m)}^{log(n)} m * \frac{n}{2^L}$ =
$n * log(m) + \sum_{L=0}^{log(n)-log(m)} m * \frac{n}{2^{L + log(m)}}$ =
$n * log(m) + \sum_{L=0}^{log(n)-log(m)} m * \frac{n}{2^{L} * m}$ =
$n * log(m) + n$ =
$n * log(m)$
这个‘我再用一个X的时候，才生成最低限度的可以完成工作的X’的思想，叫做延迟求值, lazy evalution。
是不是很有趣捏，一个看上去有难度的问题，在lazy evaluation下，平A下去就好了。
这正是Lazy Evaluation的核心优势：组合性。
更具体的说，在Lazy Evaluation下，你可以大手大脚的构建任意数据结构，而不需要担心支出。只有指定要用的部分，计算机才会花时间对之进行求值。只有在这时候，我们可以无顾虑地，从程序组合出更多的程序。
举一些实际例子：
可以用map后reduce实现Any: (a -> Bool) -> List a -> Bool，而不需要担心对整个列表进行求值
sort后对数组索引，在Lazy Evaluation下是quick select
sort后选取数组头M个元素，在Lazy Evaluation下复杂度为O(N log M)
一些高端例子：
给定一个游戏（比如国际象棋），我们可以直接生成整个游戏的game tree，然后再用各种算法（比如minmax）遍历这个game tree(why functional programming matter)
如果我们有一个A -> B的函数，我们可以生成一个键为A，值为B的，包含所有A的trie。使用这个trie，相当于调用原函数，但是会记录下中间值(Elegant memoization with functional memo tries)
tying the knot。一个数据可以在构建的过程引用自身，比如
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
或者用这来建循环数据结构，如
repeat a = a : repeat a
或者
nat = 0 : map (+1) nat
除了上面这种‘炫技’用途，你可以用tying the knot达到‘本来应该遍历两次的数据结构，只遍历一次’。
假如我们有
data Tree = Tip Int | Fork Tree Tree
一般来说，我们可以用一次遍历，找出树里面的最小值，再遍历一次，用最小值替代树里面的所有元素。
但是，如果我们用tying the knot，我们可以把这两个操作，同时进行！
repmin (Tip n) m = (Tip m, n)
repmin (Fork l r) m = (Fork tl t2, min ml m2)
where
(tl, ml) = repmin l m
(t2, m2) = repmin r m
更进一步，你可以用tying the knot玩出‘操控时间’的工作，具体见Reverse State Monad跟Tardis Monad，由于篇幅关系（我 累 了）就不详细展开了。
Lazy Evaluation额外阅读：
Using circular programs to eliminate multiple traversals of data
Algebraic Graphs with Class
Using Circular Programs for Higher-Order Syntax
Selection Functions, Bar Recursion, and Backward Induction