进来看看，求高效算法.解决方案

进来看看，求高效算法...
一数组a1,a2,……,an,定义bi=min{|ai-aj|   |   i <j <=n},bn=an,
求b1+b2+……+bn的值,求高效算法
换句话说就是，bi=ai与ai之后的所有元素的绝对值的最小值

------解决方案--------------------
从bn开始算到b1，对于任意的bi，计算bi的过程类似于对ai向a[i+1...n-1]作插入排序，这个过程可以找到bi正确的值，同时对a[i...n-1]排序。整个算法的时间复杂度为O(nlogn)，暂时没想出更好的
------解决方案--------------------
ls的复杂度是O(n^2)吧？


------解决方案--------------------
这样插入排序的复制度好像是n*n吧。

我的想法也是从bn开始，在算bi时，a[i+1...n-1]是一棵二叉树，用a[i]在二叉树中找到绝对值最小的值，同时将a[i]插入二叉树中。这样的时间复制度是nlogn
------解决方案--------------------
a[i+1....n-1] 不是一棵树。我的意思是使用这些元素建立二叉树。

找插入点当然是logn的，但是这个是数组，完成插入操作的移动却需要n。
------解决方案--------------------
即使用二分查找也是O(n^2)，移动元素是必须的；
------解决方案--------------------
象　flyingdog(flyingdog) 说的用平衡二叉树，
可以到O(nlogn)；
------解决方案--------------------
每个bi都是要求|ai-aj|最小 排序标准会变
------解决方案--------------------
从an到a1建立二叉排序树 bi就是i节点和其父节点的差的绝对值。