CODEWITHSUNDEEP
algorithmsegment-tree
Narendra Modi
Narendra Modi

Reputation: 861

Segment Tree Query for Maximum Number

I have given a an array A of n integer , and Q query in the form of X D for each query i have to find the maximum element in sub array [Ax , A(x-D),A(x-2D)..]

For example:

A = [1,2,3,4,5,6,17,8]
we have query 7 2
Sub Array [17,5,3,1] Ans=17

How can we solve this with a time complexity better than O(Q*N) since no index is updated , can it be solved offline with some technique

I don't think Square Decomposition will work here.

Upvotes: 4

Views: 582

Answers (1)

kraskevich
kraskevich

Reputation: 18546

Let D greater than sqrt(N). Then the sequence x, x - d, x - 2 * d, ... contains at most sqrt(N) elements. Thus, a naive solution works in O(sqrt(N)) per query in this case.

Let D <= sqrt(N). There are at most sqrt(N) such distinct D's. Let's iterate over them. For a fixed value d, we can compute f[i] = max(a[i], f[i - d]) for all i in linear time (boundary conditions need to be handled properly). The the answer for all queries (X, D), where D = d, is just f[X].

The total time complexity is O((N + Q) * sqrt(N)). This solution uses a linear amount of space.

Upvotes: 1

Related Questions