6

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?

Improve this question
2
  • You mean "a", "b", "c" are indexes? And are you using zero-based indexing? Commented Jun 7, 2017 at 5:52
  • @Bahrom a and b are '1' based indices, c is a number. Commented Jun 7, 2017 at 5:55

2 Answers 2

Reset to default
2

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 𝒪(log2 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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Regarding the implementation, you can define a recursive function on the tree which (1) just returns the sum of the current node if it's fully contained in the interval, (2) returns the result of the function on either the left or right child's sum if the interval is only on either the left or right side, (3) returns the sum of the function call on both the left and right children if the interval is on both sides, i.e. goes past the middle. It seems simpler than trying to split the interval fully at the start. That seems like just O(log n) per query.
Can you elaborate on how you find the actual sum of elements less than or equal to c (in O(log n))? One way to do that would be to store a cumulative sum for each node, then to do a binary search within that node to find the applicable sum.
0

  1. sort queries according to c

  2. sort array values in non-decreasing order

  3. maintain (bit|segment tree) for storing range sum

  4. before answering the current query, update index of all the array element whose value <= c

  5. answer the range-query sum problem.

Time Complexity: (n+q)*log(n), space complexity: O(n)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.