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 𝒪(n log n) space). Sort each subarray and build a cumulative sum array for it. Now your queries are 𝒪(log²n) each (log n to identify the subarrays and another log n to find the cumulative sum in each subarray).

For example, if your original array is

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

you first build this tree

            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

then sort them all

           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

Now if you want to answer query say (1,6,8) (indices are 0-based) you decompose the (1,6) interval into binary subintervals (1) (2,3) (4,5) (6) (there's no more than 2 log n of those) then find the answer for each one separately (0 for (1)={10}, 9 for (2,3)={2,7}, 4 for (4,5)={16,4}, 8 for (6)={8}) and sum them up.

Initial tree building can be done in 𝒪(n log n) if you sort pairs (value, index) once and then just pass over the sorted array log n times (once for each tree level) and copy the values to their respective nodes.