CODEWITHSUNDEEP
algorithmdata-structuressegment-treerange-query
Ivankovich
Ivankovich

Reputation: 81

Finding a range satisfying a property in faster than linear time

Given an array A[] we need to find a range which has the maximum size and its minimum element is >= 1. We also need to update this range by decreasing all its elements by 1.

One idea I got is to keep a segment tree for efficient updates. But how do I get the range in <= logarithmic time?

Maybe we can use binary search here.

Thanks

Upvotes: 0

Views: 94

Answers (1)

algojava
algojava

Reputation: 753

It's very interesting problem and I think it can be solved using Segment Tree.

Here are my idea (I hope it works fast enough):

For each segment, we need to store 4 info:

  • leftmost index of number < 1
  • rightmost index of number < 1
  • max size for this segment (store as range a and b)
  • lazy flag (true/false)

When we want to query max size, we can do recursive call to calculate the final answer. Assume our method was calcAnswer(left,right).

resA = calcAnswer(left, mid);

resB = calcAnswer(mid+1,right);

Max size will be max(resA.max_size, resB.max_size, combine(resA.right_index,resB.left_index)).

If the number of elements in array A[] are small (N<=50000), we can use Mo's Algorithm.

Upvotes: 1

Related Questions