子阵列查询

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

给出一组数字和一些查询.每个查询都会给出三个数字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)),但速度不够快.我在寻找更好的算法.我认为查询的平方根分解是行不通的.有没有更好的算法来解决这个问题？

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