- 主题:求动态区间k大 (转载)
不明白你说什么。本来每次查询就是不同的呀。
【 在 Analog (模拟人生) 的大作中提到: 】
: 标 题: Re: 求动态区间k大 (转载)
: 发信站: 水木社区 (Wed Jun 10 08:16:13 2020), 站内
:
: 问题每次区间范围都会变的啊，而且存在修改操作，要不你再考虑一下吧
: 【 在 here080 的大作中提到: 】
: : 可以先查出3或者7对应的排序，然后区间内的统计就变成全局统计了。
: : 【 在 Analog (模拟人生) 的大作中提到: 】
: : : 标 题: Re: 求动态区间k大 (转载)
: : ....................
:
: - 来自「最水木 for iPhone 6s」
: --
:
: ※ 来源:·最水木 客户端·[FROM: 223.104.212.*]
--
FROM 76.126.252.*
【 在 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.*
【 在 ylh1969 的大作中提到: 】
:
: 找到i<=7的节点(检查下i>=3)。这个是第一大。
: 再找<i的节点，就是第二大的。
: ...................
int64_t b,e,i;
T_Tree *root,*result;
// 装载root；
b=3;
e=7;
result=BB_Tree_LTEQ(root,&e,sizeof(e),int64_cmp);
if(!result) {
// 没找到
}
i=(int64_t)result->Content;
if(i<=b) {
//出界了
}
result=BB_Tree_LT(root,&i,sizeof(i),int64_cmp);
if(!result) {
// 没找到
}
i=(int64_t)result->Content; //i就是要找的
--
修改:ylh1969 FROM 123.118.54.*
FROM 123.118.54.*
你搞笑吧，比如初始化10个数
3 2 5 7 6 4 1 9 8 10
第一次查询 3 7 2 应该返回4
第二次为修改 5 8，此时序列变成3 2 5 7 8 4 1 9 8 10
第三次为查询 4 9 3，此时应该返回7
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 不行吧，现在让你求的是区间第k大，比如10个数，每次给你一个区间比如3，7，求这个区间内第二大的数据
:
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 180.164.182.*
【 在 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.*
老兄，给的是区间的位置啊
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 你搞笑吧，比如初始化10个数
: : 3 2 5 7 6 4 1 9 8 10
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 180.164.182.*
【 在 Analog 的大作中提到: 】
: 老兄，给的是区间的位置啊
: - 来自「最水木 for iPhone 6s」
无序数组的下标？
那么，将这一段数据加入二叉树，
进行一次MAX，再进行一次LT。或者N次LT。
--
修改:ylh1969 FROM 123.118.54.*
FROM 123.118.54.*
你的时间复杂度还有保证吗？
【 在 ylh1969 的大作中提到: 】
: 【 在 Analog 的大作中提到: 】
: : 老兄，给的是区间的位置啊
: ....................
- 来自「最水木 for iPhone 6s」
--
FROM 180.164.182.*
【 在 Analog 的大作中提到: 】
: 你的时间复杂度还有保证吗？
: - 来自「最水木 for iPhone 6s」
加入是n(log(n))
查询是log（n)
n是这一段数据的数量。
--
FROM 123.118.54.*
【 在 Analog 的大作中提到: 】
: 你的时间复杂度还有保证吗？
: - 来自「最水木 for iPhone 6s」
可以把这一段数据弄一个数组，排序，找最大的N个。排序的复杂度也是nlogn
--
修改:ylh1969 FROM 123.118.54.*
FROM 123.118.54.*