Search code examples
arraysalgorithmtreebitsegment

Finding the largest array index with negative value

Given an array of positive elements (1 based indexing), you have to process two types of queries:

  1. (V) find the sum of numbers in the range 1:V (both inclusive)
  2. (V, X) subtract the number X to from all in the range 1:V and report the largest index i in range 1:V such that the value at that index is negative, where the answer for this query is 0 if no such index exists.

I can do the first query using fenwick tree or segment tree but how do i support second query? I have already tried an O(n) time per query approach just checking each element in range 1...V but it times out. I need to process 10^5 such queries over an array of size 10^5.

Solution

  • Use a segment tree, such that every node stores the minimum value in its range and also the sum of the elements in its range. First query can be done directly in logn time complexity. For the second query, first subtract the given value from every element in the range (logn again) and then query for the rightmost value less than 0 (logn too).

    EDIT: A better explanation

    So first build a segment tree such that the leaves store the original value in the array. Every other node is built with two values: totalsum and minval. Build that easily with this equation: 

    segment_tree[id].minval = min(segment_tree[id*2].minval, segment_tree[id*2+1].minval)
segment_tree[id].totalsum = segment_tree[id*2].totalsum + segment_tree[id*2+1].totalsum

    The build takes O(n).

    Query A: Finding the sum in some range is easy, just find the topmost ranges relevant to your query range and add them up. Time O(logn) per query.

    Query B: Separate this query into two operations:

    A) Subtracting X from a range: Let's say you subtract X from some range [a,b]. So the total sum of [a,b] becomes old_totalsum[a,b] - (b+1-a)*X and the new minimum value becomes old_minval[a,b] - X. The key is you again do it only on the topmost ranges of your segment tree that are under the query range, so that the operation takes only logn complexity. There's slightly more to this technique, you should read it online if you aren't familiar with it already (it's called Lazy Propagation).

    B) Check the rightmost index with value < 0: Start your query on the root of the segment tree. Is the minimum value of the rightchild < 0? Then go there. Else is the minval of the leftchild < 0? Then go to the left child. If children have minval > 0, return -1. Once you reach a leaf, just return the index the leaf corresponds to. So you traverse once along the height of the tree, again O(logn).

    So total complexity of the program would be O(n + Q.logn), where Q is the number of queries.