Segment Tree : each query requires updating all nodes

Question

Given an array where each element contains 2 numbers : a(i),b(i) i.e

array[0] = pair(a(0),b(0))...

array[i] = pair(a(i),b(i))

There are two type of operations :

UPDATE i,c,d : array[i] = pair(c,d) i.e array[i] is updated to new pair

QUERY x : Find maximum of all : (a(i))*x + b(i)

I created a segment tree with each node as pair of ((a(i)),(b(i)))

Now my doubt is since every query requires multiplying first member of each node of segment tree with x , complexity for each query turns to be O(n)

How can I reduce the complexity to O(log n ).

Answer 1

Order the array by a[i]. Build the set of the top edges using a Graham scan. Basically start with the first edge, then every time you add an edge check if the previous one remains visible and remove it if not, and repeat until the previous one remains visible.

Once you have the set, store the points where you switch from one line to another (intersections between the visible lines). Then for a query do a binary search to figure out between which point it falls and take the line there O(log N).