Subarray queries

Question

So I was trying to solve this programming problem.

Given an array of numbers and some queries. Each query gives you three numbers a,b,c and asks you to answer sum of all elements from index a to index b (both included) that are less than or equal to c.

for example:

Given array: {2,4,6,1,5,1,6,4,5,4}

3 queries are to be answered:

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

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

4 5 1 -> ans=1

each value in the array is less than 10^5, the length of array and the number of queries could range upto 10^5

Here's what I did I used Mo's algorithm(Square root decomposition) to sort the queries, and created a Binary indexed tree to store the cumulative sum of the elements less than all the values from 1-10^5, and made an update moving from queries to queries. With this algorithm the overall complexity of my solution is O(q*sqrt(N)*log(N)) but it is not fast enough. I was looking for a better algorithm. I think square-root decomposition of queries wouldn't work. Is there any better algorithm to solve this problem?

I was wondering if some data-structure could solve this problem that I am unaware of?

Answer 1

You can decompose it the other way around. Namely, build a tree of half-arrays (this is

查看更多

0人赞 添加讨论(0) 举报