【 在 Analog 的大作中提到: 】
: 不行吧，现在让你求的是区间第k大，比如10个数，每次给你一个区间比如3，7，求这个区间内第二大的数据

找到i<=7的节点(检查下i>=3)。这个是第一大。
再找<i的节点，就是第二大的。
每次查找都是O(log(n)).

这组平衡二叉树工具可用。

//返回=key的节点
T_Tree * BB_Tree_Find(T_Tree *sp,void *content_key,int len,
                int (*Cmp_rec)(void *sp_content,void *content_key,int len));
//返回>key的节点
T_Tree * BB_Tree_GT(T_Tree *sp,void *content_key,int len,
                int (*Cmp_rec)(void *s1,void *s2,int len));
//返回>=key的节点
T_Tree * BB_Tree_GTEQ(T_Tree *sp,void *content_key,int len,
                int (*Cmp_rec)(void *s1,void *s2,int len));
//返回<key的节点
T_Tree * BB_Tree_LT(T_Tree *sp,void *content_key,int len,
                int (*Cmp_rec)(void *s1,void *s2,int len));
//返回<=key的节点
T_Tree * BB_Tree_LTEQ(T_Tree *sp,void *content_key,int len,
                int (*Cmp_rec)(void *s1,void *s2,int len));
--
修改:ylh1969 FROM 123.118.54.*
FROM 123.118.54.*

【 在 Analog 的大作中提到: 】
: 你搞笑吧，比如初始化10个数
: 3 2 5 7 6 4 1 9 8 10
: 第一次查询 3 7 2 应该返回4
: ...................
二叉树是按大小排序的。
修改后依然是新的序。
此工具的修改方法是，删除原节点，加入新节点。
O（logn）
--
修改:ylh1969 FROM 123.118.54.*
FROM 123.118.54.*

【 在 Analog 的大作中提到: 】
: 你的时间复杂度还有保证吗？
: - 来自「最水木 for iPhone 6s」
加入是n(log(n))
查询是log（n)
n是这一段数据的数量。
--
FROM 123.118.54.*

【 在 Analog 的大作中提到: 】
: 不行，需要各种操作都是O(logn*logn)
: - 来自「最水木 for iPhone 6s」
世界上有这种技术吗？
nlogn已经是各种排序技术的极限了。
我的方法，n已经是区间数据量了，比数据全集已经小了好多。
--
修改:ylh1969 FROM 123.118.54.*
FROM 123.118.54.*

【 在 Analog 的大作中提到: 】
: 不行，需要各种操作都是O(logn*logn)
: - 来自「最水木 for iPhone 6s」
还一个方法：
K大的buffer。
在区间内搜索一次。最大的k个在k-buffer里进行插入排序。
如果k足够小，空间开销忽略，时间是O（n)，n=选择的数据集。
虽然O数不小，但是实际运行时间跟拷贝n个数据差不多。可以不必纠结O数。
如果n足够小，远远小于全集，可以认为是O（1）。
就是说，时间与全集的大小无关，只与选择集有关。
你开发的任何算法，都免不了拷贝一遍数据。这时间就算完了，你认为是O（0）都是合理的。
--
修改:ylh1969 FROM 123.118.54.*
FROM 123.118.54.*