标签: range-query

假设我有一个长度为L的数组A.我将给出n个区间(i,j)并且我必须递增A [i]和A [j]之间的所有值.哪个数据结构最适合给定的操作？
间隔是事先已知的.

我不完全了解Cassandra的一个主要部分是它的范围查询.我知道Cassandra强调分布式环境并专注于性能,但可能正是因为它,它目前只支持几种类型的范围查询,它可以有效地完成,我想知道的是:支持哪种类型的范围查询由卡桑德拉.

据我所知,Cassandra支持以下范围查询:

1:主键上带有关键字的范围查询TOKEN,例如:

 CREATE TABLE only_int (int_key int PRIMARY KEY);
 ...
 select * from only_int where token(int_key) > 500;

2:使用关键字在辅助索引上具有一个相等条件的范围查询ALLOW FILTERING,例如:

CREATE TABLE example (
  int_key int PRIMARY KEY,
  int_non_key int,
  str_2nd_idx ascii
);
CREATE INDEX so_example_str_2nd_idx ON example (str_2nd_idx);
...
select * from example where str_2nd_idx = 'hello' and int_non_key < 5 allow filtering;

但我想知道我是否遗漏了一些东西,并寻找一个规范的答案,其中列出了当前CQL支持的所有类型的范围查询(或者一些允许更多类型的范围查询的解决方法).

假设我正在跟踪Fenwick树中插槽的使用情况.例如,让我们考虑跟踪32个插槽,导致Fenwick树布局,如下图所示,其中网格中的数字表示底层数组中的索引,其中计数由Fenwick树操纵,其中每个单元格中的值为该段中"已使用"项的总和(即阵列单元23存储范围[16-23]中使用的时隙量).最低级别的项目(即单元格0,2,4,...)只能具有值"1"(使用的槽)或"0"(空闲槽).

我正在寻找的是一种有效的算法来查找给定数量的连续空闲时隙的第一个范围.

为了说明,假设我有如下图所示的Fenwick树,其中总共使用了9个插槽(请注意,为了清晰起见,仅添加浅灰色数字,而不是实际存储在树的数组单元中).

现在我想找到例如10个空闲插槽的第一个连续范围,它应该找到这个范围:

我似乎无法找到一种有效的方法,这让我有点头疼.请注意,由于所需的存储空间量对我的目的而言至关重要,因此我不希望将设计扩展为细分树.

对O(log N)类型的解决方案的任何想法和建议都将非常受欢迎.

编辑

赏金期限到期后的更新时间.感谢所有意见,问题,建议和答案.他们让我重新思考问题,教会了我很多并向我指出(再一次,有一天我可以学到这一课),我应该更多地关注我在提问时要解决的问题.

由于@Erik P是唯一一个对包含所请求的代码/伪代码的问题提供合理答案的人,因此他将获得赏金.

他还正确地指出使用这种结构的O(log N)搜索是不可能的.荣誉对@DanBjorge提供一个证明,让我想想最坏情况下的性能.

@EvgenyKluev的评论和回答让我意识到我应该以不同的方式提出我的问题.事实上,我已经在很大程度上做了他的建议(参见https://gist.github.com/anonymous/7594508 - 显示我在发布此问题之前遇到的问题),并问这个问题,希望能有效率搜索连续范围的方法,从而防止将此设计更改为段树(这将需要额外的1024字节).然而,似乎这种改变可能是明智之举.

对于任何感兴趣的人,可以在这里找到与此问题中使用的示例匹配的二进制编码Fenwick树(以64位编码的32插槽fenwick树):https://gist.github.com/anonymous/7594245 .

我正在尝试解决这个问题：https : //cses.fi/problemset/task/1144/

给定一个最多200000包含元素的数组，我的任务是处理最多200000查询，这些查询要么让我更新数组中的单个值，要么让我找到给定范围内的 a 和 b 之间的元素数（对于例如，查询会询问从索引1到5范围内有多少元素[2, 3]）。

我目前的想法是首先对给定数组中的值使用索引压缩（因为值可以高达10^9，因此保留一个简单的出现数组会超出存储限制），然后保留另一个包含每个压缩出现次数的数组数字。然后，可以使用求和段树来处理和更新查询。

但是，我在尝试实施这种方法时遇到了问题。我意识到更新单个数组值会迫使我更改压缩数组。

例如，给定一个数组[1, 5, 3, 3, 2]，我将定义一个压缩函数C，使得

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;

然后，出现数组将是[1, 1, 2, 1]，并且处理总和查询将是有效的。但是，如果我被指示更新一个值，例如，将第三个元素更改为4，那么这会使所有内容失去平衡。压缩功能必须更改为

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;

这将迫使我重建我的事件数组，从而导致O(N)更新时间。

由于N可以达到200000，我目前的方法不能有效地解决问题，尽管我认为我对索引压缩有正确的想法。有人可以用我的方法指出我正确的方向吗？

我建立了一个d维度 KD 树。我想在这棵树上进行范围搜索。维基百科提到了 KD 树中的范围搜索，但没有以任何方式谈论实现/算法。有人可以帮我解决这个问题吗？如果不是任意的d，至少对d = 2和的任何帮助d = 3都会很棒。谢谢！

上下文

我有一个应用程序从表中选择加权随机条目,其中前缀总和(权重)是关键部分.简化的表定义如下所示:

CREATE TABLE entries (
    id INT NOT NULL PRIMARY KEY AUTO_INCREMENT,
    weight DECIMAL(9, 3),
    fenwick DECIMAL(9, 3)
) ENGINE=MEMORY;

其中`fenwick`存储Fenwick树表示中的值`weights`.

让每个条目的"范围"跨越其前缀和与其前缀sum +其权重之间.应用程序必须@r在0和之间生成一个随机数,SUM(weight)并查找其范围包含的条目@r,如下所示:

Fenwick树,结合MEMORY引擎和二进制搜索,应该允许我及时找到合适的条目O(lg^2(n)),而不是O(n)天真查询的时间:

SELECT a.id-1 FROM (SELECT *, (@x:=@x+weight) AS counter FROM entries 
    CROSS JOIN (SELECT @x:=0) a
    HAVING counter>@r LIMIT 1) a;

研究

由于多个查询的开销,我一直在尝试将前缀sum操作压缩成一个查询(而不是脚本语言中的几个数组访问).在这个过程中,我意识到传统的求和方法,即涉及按降序键顺序访问元素,只会求和第一个元素.我怀疑MySQL在WHERE子句中存在变量时会线性地运行表.这是查询:

SELECT
SUM(1) INTO @garbage
FROM entries 
CROSS JOIN (
    SELECT @sum:=0,
        @n:=@entryid
) …

有很多关于最近邻搜索问题的工作,所以我想知道我是否想要进行固定半径范围搜索,我可以利用这些算法进行最近邻搜索吗？

也许我可以一遍又一遍地进行第k次最近邻搜索,直到找到超出半径范围的点,但我想这可能会造成很多浪费.

试图找出如何做到这一点.基本上我想按提交的小时/日/月/年排序.

每个submission都有一个created字段,其中包含一个形式为的Mongoose Date对象"created" : ISODate("2013-03-11T01:49:09.421Z").我是否需要在find()条件下与此进行比较？

这是我当前的查询(我将其包装为分页目的FWIW,所以只是忽略该部分):

  getSubmissionCount({}, function(count) {

  // Sort by the range
    switch (range) {
      case 'today':
        range = now.getTime();
      case 'week':
        range = now.getTime() - 7;
      case 'month':
        range = now.getTime() - 31; // TODO: make this find the current month and # of   days in it
      case 'year':
        range = now.getTime() - 365;
      case 'default':
        range = now.getTime();
    }

    Submission.find({
      }).skip(skip)
         .sort('score', 'descending')
         .sort('created', 'descending')
         .limit(limit)
         .execFind(function(err, submissions) {
            if …

我们在2D平面上给出N(N <= 10 ⁶)个点并且给出整数D(N <= 10 ⁶),我们想要找到两个点p1,p2(p1右边的p2)使得它们之间的差异p1.y并且p2.y至少是D并且p2.x - p1.x被最小化.

x轴和y轴的范围为0..10 ⁶

这是USACO过去的比赛中的一个问题.

这是我尝试解决它:
MAXY = N个点中的最大y轴.
假设我们知道p1,那么我们很容易找到p2; 通过将其y轴在该范围内的所有点都设置p1.y+D为MAXY或在0到0的范围内,p1.y-D并获取具有最大x轴的点大于p.x.这将是p2的最佳选择.

但是由于我们不知道p1,我们将不得不尝试p1的所有点,因此找到p2的最佳选择应该有效地完成.

我使用了一个分段树.树中的每个节点都将按照x轴的排序顺序存储相应范围内的所有点.在查询时,如果一个节点落在查询范围内,那么我们在数组上进行二进制搜索,p1.x并返回大于它的最小元素.

对于p1的每个选择,我们使用范围0,p1.yD和p1.y + D,MAXY两次查询树,并且在返回的两个点中取最佳值.

树的构建可以在O(NlogN)时间内完成.每个查询都需要O(logN*logN)时间,我们进行N次查询,因此所用的总时间为(Nlogn*logn),可能不会在2秒的时间限制内运行.(10 ⁶*20*20).所采用的存储器也将是O(NlogN),其大约为80mb(100000*20*4kb),这太大,因为限制是64mb.

我们如何更快地进行查询并使用更小的空间？

我在最近的一次采访中得到了这个问题:给定一个BST,其节点包含一个Integer作为值,找到其节点落在整数X(min)和Y(max)之间的所有子树,其中X <Y.这些子树不能相互重叠.

我已经解决了这个问题的变化,例如 - 打印在给定范围内的BST的键.但无法弄清楚这一点,因为它涉及查找满足非常特定约束的主图/树的所有连通子图.任何指针/帮助/伪代码都很受欢迎.

补充说明 -

1. 该问题将节点的数据结构定义为具有左指针,右指针和整数值.没有办法标记节点.
2. 有人要求用Java解决这个问题.
3. 当我说子树/子图时,我的意思是一组连接的节点,而不是一个不相交的节点列表.对困惑感到抱歉.