子阵查询

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

这是我所做的我用莫氏算法（平方根分解）对查询进行排序，并创建一个二进制索引树，用于存储元素累积和小于1-10^5中所有值的元素，并使更新从查询移动到查询。使用这种算法，我的解决方案的总体复杂度为O（q * sqrt（N）* log（N）），但速度不够快。我正在寻找更好的算法。我认为查询的平方根分解不起作用。有没有更好的算法来解决这个问题？

我想知道如果一些数据结构可以解决这个问题，我不知道？

Answer 1

你可以反过来分解它。即建立一个半阵列树（这是（n log n）space）。对每个子数组进行排序并为其构建累积和数组。现在，你的查询都是（日志 ñ）各（日志ñ识别子阵列和其他日志ň找到每个子阵列的累计总和）。

例如，如果你原来的数组是

  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）（这里（1）= {10}为0，（2,3）= {2,7}为9，（4,5）为4则分别找到答案）= {16,4}，对于（6）= {8}为8）并且将它们相加。

初始树建设在（ñ日志ñ）来完成，如果你排序对（价值指数）一次，然后就通过对有序阵列日志n次（一次为每个树级别）及复印件值分配给它们各自的节点。