Assume that initially in array each element has infinity as value.

Now M queries are input of the type l r x.

Here l to r is range where value need to be updated if a[i]>x where l<=i<=r. and l<=r<=n

After M queries you need to output the minimum value at each index.

One way to this is to use Brute Force

     scanf("%d %d %d",&l,&r,&c);
            if(a[i]>c )



Now this takes O(mn) time where n=size of each query which can be n in worst case.

What are more efficient ways to solve this in lesser time complexity?

  • 1
    $\begingroup$ I can't understand the problem you're trying to decribe. You say that a value needs to be updated under certain conditions but you don't say what it's updated to. $\endgroup$ – David Richerby Jul 12 '15 at 15:38
  • 1
    $\begingroup$ Very similar question; duplicate? $\endgroup$ – Raphael Jul 12 '15 at 17:29

It can be done by using Segment Tree data structure:

  1. Originally described query is just "lowering values at some segment", so let's call it update query. To perform this query you need to update at most $O(log N)$ segments and it also can be done with $O(log N)$ time-complexity. So for run all update queries we need $O(N log N)$ time.
  2. We have another type of query "what is the value at $a[i]$. In general we can answer to such query with $O(log N)$ time, by going through all segments that contains $a[i]$ and take minimum from such values and due to nature of segment tree there will be at most $\lceil log N \rceil$ such segments. At this point we have online solution (e.g. queries of 1st and 2nd types can be mixed). Also gathering resulting array after all queries of 1st type (e.g. offline solution that asked in original post) can be performed even with $linear$ complexity(relatively to array length); please, note that it's time complexity only for constructing result array by segment tree, for performig $N$ queries we still need $O(N log N)$ time.

For example:

  1. To perform update query on segment $[1, 4]$ you need to update pink nodes.
  2. To know what is value at $a[4]$ you need to go through all segments rounded by yellow and takes minimum from values at this segments.


| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.