ProdipDatta's blog

Range Query on Li Chao Tree ??
By ProdipDatta, history, 4 years ago, In English

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.

  • Vote: I like it
  • +29
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 4   Vote: I like it +17 Vote: I do not like it

Think of LiChao as a replacement of CHT. Now consider how you would answer queries of this type if you used CHT instead. Well that actually isn't so hard.

The lower hull is clearly convex, hence we can notice that the answer to some query defined by [L, R], will be the maximum of:

  • query(L)

  • query(R)

Well now consider using LiChao tree. You can use the exact same queries and then your queries can be solved in 2 normal LiChao queries.

PS: This is correct because of convexity applied for L and R.

Convexity states that for any $$$\alpha \in [0, 1]$$$ and any two $$$x_1, x_2$$$, we have:

$$$\alpha * f(x_1) + (1 - \alpha) * f(x_2) \geq f(\alpha * x_1 + (1 - \alpha) * x_2)$$$

Therefore, if we apply it for L, R and f(x) = query(x), we can see that for every $$$x \in [L, R]$$$, $$$f(x) \leq \max(f(L), f(R))$$$.

→ Reply