你认为最优美的数据结构是什么？
Finger tree是个理论上好用数据结构. 我不知道看到了多少篇paper只要用finger tree的话几句话就可以了. 我是准备哪一年有时间好好写一个survey. 这个来自于paper. (实际上有一系列更早的paper, 但是PL的人给出的抽象的描述比较好用. finger tree实际上和finger search tree/finger search有关... 可以做到以下的几个抽象功能: Finger tree是用来储存一个sequence的S=s_1,\ldots,s_n. 这里每个元素来自于 (M,\cdot), 一个monoid. 我们假设如果a,b in M, 则计算ab只需要O(1)时间. 1. split(S,p), p:M\to \{0,1\}
is a 单调predicate, 也就是说p(ab)\geq p(a)
. 将sequence s_1,\ldots,s_n 拆成s_1,\ldots,s_t以及s_{t+1},\ldots,s_n. 这里t满足 p(\prod_{i=1}^j s_i) = 0
, 如果j < t. 且 p(\prod_{i=1}^j s_i) = 1如果j\geq t. 耗时 O(\log \min(n,n-t)). 2. concat(s_1,\ldots,s_n; t_1,\ldots,t_m): 获得新的sequence s_1,\ldots,s_n,t_1,\ldots,t_m. 耗时O(\log \min(n,m)) 3. product(S), 获得\prod_{i=1}^n s_i, O(1)时间. 4. map(S,f), 获得sequence f(s_1),\ldots,f(s_n). O(1)时间. (这里我们要求这个函数f满足某些特殊的属性, 比如给函数f和g, 可以O(1)时间计算函数h = f\circ g. 并且这个函数h也能在O(1)时间evaluate. 还有一个要求是f可以保证可以通过product(S)在O(1)时间获得product(f(s_1),\ldots,f(s_n)).   [这个原来的paper里没有, 可以利用lazy propagation来支持, 这里O(1)可以变成其他的东西, 但是整个数据结构很多地方相应的要有改变...] 当然, 还需要一个O(1)时间创建一个只有一个元素的sequence的方法. 多少篇paper实际上只需要说"用finger tree,里面的monoid是xxx"就好了. 选对了monoid. 可以保证只要几行代码就能实现以下的东西. - 可以用来代替树状数组. 而且还能提供insert/delete呢. - 可以做concatenatable deque, 并且还能同时计算整个deque里所有元素的sum. - priority queue - rope - 我感觉这个paper里的东西可以解决 - 这个arxiv文里的log-list的功能似乎就是个finger tree... 这样它的几个application都可以直接拿finger tree用. - 我还 写过两个稍微少见点的功能, 比如optimal的list merge的时间, klee measure问题.