For every fixed $d \in \mathbb{N}$, we design a data structure that represents a binary $n \times n$ matrix that is $d$-twin-ordered. The data structure occupies $O_d(n)$ bits, which is the least one could hope for, and can be queried for entries of the matrix in time $O_d(\log \log n)$ per query.


翻译:对于每个固定的 $ d $ $\ mathbb{N} $,我们设计一个数据结构,它代表一个二进制 $n\ times n$ 矩阵,由 $- $- twin 顺序排列。数据结构占用了 $_ d(n) 位元,这是人们最不希望得到的,并且可以对每个查询的输入及时查询$O_ d(\log\log n) 。

0
下载
关闭预览

相关内容

Google-EfficientNet v2来了!更快,更小,更强!
专知会员服务
18+阅读 · 2021年4月4日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
已删除
将门创投
4+阅读 · 2020年1月6日
VIP会员
相关资讯
已删除
将门创投
4+阅读 · 2020年1月6日
Top
微信扫码咨询专知VIP会员