Updating a range and keeping track of the maximum value that occurs at every index

Question

You are given an array, say A[], of N elements, initially all of them are equal to negative infinity.

Now you are asked to perform two types of queries(Total M queries):

Type 1. Given two integers a and d you need to update the array A[] from index l to index r. What you need to do exactly is - for each index l+i (where 0<=i<=r-l) which contains some value say 'val' you need to update the value of that index with maximum of a+i*d and val, i.e, A[l+i] = max(A[l+i], a+i*d).

Type 2. Given an integer 'i', you need to report the value of A[i].

Example : let N = 5 and M = 4

initially A[] = {-inf, -inf, -inf, -inf, -inf}
query 1: l = 2, r = 4, a = 2, d = 3
new A[] = {-inf, 2, 5, 8, -inf}
query 2: i = 3
output = 5
query 3: l = 3, r = 5, a = 10, d = -6
new A[] = {-inf, 2, 10, 8, -2}
query 4: i = 5
output = -2

Note : value of N and M can be as large as 100000 so I am looking for better algorithms than O(N*M).

Thanks.

Answer 1

Think about the problem this way: You are managing a collection of piecewise linear functions f_i(x) = a_i x + b_i (l_i <= x <= r_i) subject to the following operations:

• Add a new function
• Find the maximum of all the functions added so far that are defined for a specific value of x

I see two possible approaches:

1. Store only the maximum ("upper hull") of all the functions, which is in turn a collection of piecewise linear functions, but with disjoint definition intervals. UPDATE: I initially thought this could be done with a simple binary search tree, but it's not as simple as that, so I would go with option 2
2. Follow a more standard approach and use a segment tree on the x range (the "array"), that stores sets of linear functions in its nodes. Now for a given x, you can walk up the tree to find out what linear functions are defined at that point and use the standard convex hull trick to find their maximum at x. Complexity: O(n + M * log n * log M)