In sorted range selection problem, the aim is to preprocess a given array A[1: n] so as to answers queries of type: given two indices i,j ($1 \le i\le j \le n$) and an integer k, report k smallest elements in sorted order present in the sub-array A[i: j] Brodal et.al.[2] have shown that the problem can be solved in O(k) time after O(n log n) preprocessing in linear space. In this paper we discuss another tradeoff. We reduce preprocessing time to O(n), but query time is O(k log k), again using linear space. Our method is very simple.


翻译:在排序范围选择问题中,目标是预处理给定的阵列 A[1: n],以便回答类型查询:给两个指数i、j(1 \ le i\ le j\ le n$)和整数 k,报告A[ j] Brodal etal. 等次阵列中出现的按顺序排列的 k 最小元素。[2] 已经显示,在O(k) 时间后,在线性空间的 O(n log n) 预处理可以解决问题。在本文中,我们将讨论另一个取舍。我们把预处理时间缩短到 O(n),但查询时间是 O(k log k),使用线性空间。我们的方法非常简单。

0
下载
关闭预览

相关内容

专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
26+阅读 · 2020年9月9日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
164+阅读 · 2020年3月18日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
美国化学会 (ACS) 北京代表处招聘
知社学术圈
11+阅读 · 2018年9月4日
人工智能 | AAAI 2019等国际会议信息7条
Call4Papers
5+阅读 · 2018年9月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2021年5月29日
VIP会员
相关VIP内容
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
26+阅读 · 2020年9月9日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
164+阅读 · 2020年3月18日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
相关资讯
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
美国化学会 (ACS) 北京代表处招聘
知社学术圈
11+阅读 · 2018年9月4日
人工智能 | AAAI 2019等国际会议信息7条
Call4Papers
5+阅读 · 2018年9月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员