子阵列查询

Question

所以我试图解决这个编程问题.

给出一组数字和一些查询.每个查询都会给出三个数字a,b,c,并要求您回答索引a到索引b(包括两者)中小于或等于c的所有元素的总和.

例如:

给定阵列:{2,4,6,1,5,1,6,4,5,4}

将回答3个查询:

2 4 4 - > ans = 5即{4 + 1}

1 5 3 - > ans = 3即{2 + 1}

4 5 1 - > ans = 1

数组中的每个值小于10 ^ 5,数组的长度和查询的数量可以达到10 ^ 5

这就是我所做的我用Mo的算法(平方根分解)对查询进行排序,并创建了一个二进制索引树,用于存储元素的累积和小于1-10 ^ 5中的所有值,并进行了更新.对查询的查询.使用这种算法,我的解决方案的整体复杂性是O(q*sqrt(N)*log(N)),但速度不够快.我在寻找更好的算法.我认为查询的平方根分解是行不通的.有没有更好的算法来解决这个问题？

我想知道是否有一些数据结构可以解决我不知道的这个问题？

Answer 1

你可以用相反的方式分解它。即，构建一棵半数组树（这是 ( n log n ) 空间）。对每个子数组进行排序并为其构建一个累积和数组。现在您的查询是 (log ² n ) 每个 (log n来标识子数组和另一个 log n用于查找每个子数组中的累积和）。

例如，如果您的原始数组是

            5,10,2,7,16,4,8,9

你首先构建这棵树

            5,10,2,7,16,4,8,9
              /         \
      5,10,2,7           16,4,8,9
      /      \           /      \
    5,10     2,7      16,4      8,9
    / \      / \      / \       / \
   5   10   2   7   16   4     8   9

然后将它们全部排序

           2,4,5,7,8,9,10,16
              /         \
      2,5,7,10           4,8,9,16
      /      \           /      \
    5,10     2,7      4,16      8,9
    / \      / \      / \       / \
   5   10   2   7   16   4     8   9

现在，如果您想回答查询 (1,6,8)（索引从 0 开始），您可以将 (1,6) 区间分解为二进制子区间 (1) (2,3) (4,5) (6) （其中不超过 2 log n）然后分别找到每个的答案（0 表示 (1)={10}，9 表示 (2,3)={2,7}，4 表示 (4,5 )={16,4}, 8 (6)={8}) 并将它们相加。

如果对（值，索引）对（值，索引）进行一次排序，然后将排序后的数组 log n 次传递（每个树级别一次）并将值复制到各自的节点，则可以在 ( n log n ) 中完成初始树构建。