math - Algorithm to find maximum value of ax + b for different values of x -

imagine array a of size n, each array element contains 2 positive integers a_i , b_i.

there q queries each query can 1 of 2 types:

1) given positive integer x, find max (a_ix + b_i) i 1 n

2) update values of a_i , b_i i

the number of queries can large hence naive o(q * n) algorithm wouldn't suffice. also, x can large 10⁹ , value of objective expression can large 10¹⁸.

can solved using variation of segment trees? if there similar question around please point me it. also, how go solving one? not looking code, hints / pointers logic.

edit: can assume values of x in query type 1 non decreasing.

edit 2: can assume in updates, value of a increases.

edit 3: have found answer question here. @mikhail pointing out word envelope. using word many times did ;-)

the @sorin's idea right, finding of intersection points inefficient. want construct upper envelope of lines. envelope contain not more n-1 points (each line can contribute not more once in envelope). scanning through sorted points take o(n+q) time.

now, construct envelope in o(nlogn) time. first of all, sort lines ascending a. take o(nlogn). let's assume simplicity values of a different, not change main idea.

note lines 0 , n-1 form left , right slopes of envelope. because near infinity, constant b not mater. let's start line 0, first segment of envelope. go through other lines in order of ascending a, updating envelope on each step. how many more times going repeat "the envelope"? hmm...

the update of envelope (damn!) quite similar how graham scan works. @ first step put line 0 in stack. on each step, consider next line , throw away lines top of stack, until new line fits. see image:

here add line i+1. need throw away lines i , i-1. since each line added stack , removed not more once, whole scan takes o(n). can see, sorting takes time.

wonder how decide whether next line fits current stack? compare points of intersections of lines i+1 on i , i on i-1.

now have envelope (i swear, last time), rest easy. have solution working in o(q+nlogn). hth.

by way, pointed out algorithm quite popular , called convex hull trick.

upd wow, forget need update envelope time time :) complicates problem. need think it.

anyway, in contrast naive approach, handles queries of type 1 in o(n) , of type 2 in o(1), offers opposite: o(1) type 1, o(n) type 2.