Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

Range Query on Li Chao Tree ??

Revision en1, by ProdipDatta, 2020-05-31 13:09:46

Hi everyone
I know that in Li Chao Tree it is possible to add some line of the form (ax + b), in the tree and query for a maximum or minimum y-intercept in a specific point, x.
I want to know that Is it possible to query for a maximum y-intercept in a range of values,x ?
More specifically, is it possible to choose such a value x from the interval [l, r] such that x gives the maximum y-intercept with complexity less than or equal to O(sqrt(N)) where 1 <= l <= r <= N <= 106 ?.

Your any kind of information regarding the topic will be appreciated.
Thank you.

Tags #data structure, #li chao tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ProdipDatta 2020-05-31 13:09:46 710 Initial revision (published)