### The problem

Let us consider the problem where we need to quickly calculate the following over some set *S* of *j* for some value *x*.

Additionally, insertion of new *j* into *S* must also be efficient.

This will most likely be encountered with DP problems. For example, the recent problem 1083E - Орехус и прямоугольники from Round #526 has the following DP formulation after sorting the rectangles by *x*.

*f*(

*i*) =

*x*

_{i}·

*y*

_{i}-

*a*

_{i}+

*max*

_{1 ≤ j < i}{ -

*x*

_{j}·

*y*

_{i}+

*f*(

*j*)}

The problem requires quick calculation of the above define maximum for each index *i*. How can this be done?

### The idea

Notice the special form of *m*_{j}·*x* + *c*_{j}. This is identical to the equation of a straight line with slope *m*_{j} and Y-intercept *c*_{j}. So the problem is equivalent to being given a set of lines and asked for the maximum *y* value any of those lines can give at a particular *x*. If you draw a bunch of straight lines on a plane, you'll notice that the maximum values are along what appears to be a convex hull.

Some observations:

- Every line on the hull provides the maximum value on some contiguous range of
*x*values. Conversely, every line not on the hull is useless and never provides the maximum. - All the lines on the hull have different slopes. The order of slopes also determines their position on the hull. A line with lower slope appears on the hull to the left of one with a higher slope.

So, a possible strategy can be to only maintain the convex hull and not keep the useless lines .

### A specific problem

Let us further consider the rectangle problem mentioned above.

For clarity, let's substitute *x* and *y* of the problem statement with *p* and *q*, and allow *x* and *y* to only refer to coordinates of the 2D plane where we consider the lines.

*f*(

*i*) =

*p*

_{i}·

*q*

_{i}-

*a*

_{i}+

*max*

_{1 ≤ j < i}{ -

*p*

_{j}·

*q*

_{i}+

*f*(

*j*)}

In this problem the slope of the lines *m*_{j} is given by - *p*_{j}. Due to the nature of the constraints (no rectangles are nested), after sorting rectangles by increasing *p* we will find they are also sorted by decreasing *q*.

The idea:

- We'll keep the lines of the hull, in sorted order of slope.
- We iterate over the rectangles from
*i*= 1 to*n*, and*p*_{i}<*p*_{j},*q*_{i}>*q*_{j}for*i*<*j*. - When we have to get the maximum at some
*x*=*q*_{i}, all lines that provide the maximum at positions >*q*_{i}are now useless, since further maximum queries are guaranteed to occur at <*q*_{i}. - When a new line is inserted, the slope of this line -
*p*_{i}is guaranteed to be lesser than all lines in the hull. Therefore, this line is also guaranteed to provide the maximum in some range ( - ∞,*x*]. However, adding this line may make it so that some lines previously on the hull are no longer on it. These lines need to be removed to maintain the hull.

For this particular problem:

**The lines are inserted in sorted order of slope****The query positions are also in sorted order**

Implementing query and insert:

**Query**

When querying at *x* = *q*_{i}, just compare the value at *x* of the rightmost line with that of the line next to it. If it is lower, remove it and repeat. When done, get the value at *x* of the rightmost line as the answer to the query.

**Insert**

When inserting a line, if the intersection point of this line and the leftmost line lies to the right of that of the leftmost line and the line to the right of it, the leftmost line is no longer on the hull. Remove it, and repeat. Parallel lines pose an exception to this since they will never intersect, and must be handled separately if such a situation is possible in the problem.

And that's it... since we add lines at one end and remove at both ends, the data structure for the job is a deque.

**Solution for the rectangle problem:**

Complexity is if *N* lines are inserted and *Q* queries are made.

##### A few what ifs

**What if slopes are sorted in increasing order instead?**

You can modify the logic accordingly.... *or* you can observe that negating the slope has the effect of mirroring lines about the Y-axis, so you can use one implementation for both.

**What if slopes are sorted but in reverse order of the query positions?**

Both adding and removing will be done at one end, so a stack is required. Of course a deque can also do the job of a stack.

**What if minimum is required instead of maximum?**

Again, you can modify the logic... *or* you can observe that negating both slope and Y-intersect has the effect of mirroring about the X-axis. You can use the same implementation.

### A more general problem

Let us consider a problem where

**The lines are inserted in sorted order of slope****The query positions are in arbitrary order**

To tackle this problem nothing needs to be changed for insertion. However we can no longer remove lines when answering queries. In order to answer queries, notice that each line provides the maximum in some range which is defined by its intersection point with the previous and next line. Given a particular *x* we can use binary search to find the line where the value will be maximum.

**Solution for the rectangle problem using this method:**

Complexity is .

### The original problem

Coming back to the general version,

**The lines are inserted in arbitrary order of slope****The query positions are in arbitrary order**

This is referred to as the "fully dynamic" version of CHT. A convenient way to implement this is using a sorted set, such as `std::set`

in C++ or `TreeSet`

in Java. The idea is to maintain the set sorted by slope. To query, binary search is used as before. To insert, the position at which the line should be inserted is located. If this line does not appear on the hull, it is not inserted. If it does, useless lines are removed from both the left and right of the inserted line. The complexity using this method is .

You can find a neat implementation here (thanks to Chilli for the link). A couple more can be found here and here. I do not want to go into further details about this method, because I personally find using Li Chao tree much simpler if the fully dynamic version is required. Li Chao tree is a specialized segment tree that also deals with the convex hull trick, and there exists a nice tutorial for it on cp-algorithms. This page also contains an alternate interpretation of CHT.

### Conclusion

Although this tutorial focuses on the technique of CHT, it is worth mentioning that in contests CHT will almost always be intended as a way to optimize DP. You can refer to link titled "Dynamic Programming Optimizations" below to check out the forms of DP recurrences that can be optimized this way.

**Note about precision**: You may have noticed that the function `intersectX`

in the code uses `long double`

to find the coordinate. Is this good enough? Since queries are (usually) at integer *x*, the lines which provide the maximum in a range completely contained in interval between two consecutive integers are useless since they never provide a maximum at any integer coordinate. So we actually do not even need `long double`

, floor/ceil division will do just fine. Thanks to tmwilliamlin168 for pointing this out to me. Note that integer division is not the same as floor division in C++ for negative numbers.

##### Useful links

- Convex hull trick (PEGWiki)
- Convex hull trick and Li Chao tree (cp-algorithms)
- Algorithms Live — Convex Hull Optimization (YouTube)
- Dynamic Programming Optimizations
- Fully Persistent Convex Hull Trick

##### Problems

Ordered approximately by difficulty:

- 1083E - Орехус и прямоугольники
- 319C - Калила и Димна на лесозаготовках
- CYCLRACE – Cyclist Race
- Covered Walkway
- Machine Works
- Squared Ends
- 631E - Мультипликативная сумма
- 1388E - Дядя Богдан и Проекции
- 932F - Сбежать через лист
- 311B - Транспортировка кошек
- Avoiding Airports
- JUMP – Jump mission
- PDELIV – Pizza Delivery
- YATP
- POLY – Polynomials
- WEASELSC – Weasel finds Staircase

That concludes my first tutorial on Codeforces. Thanks for reading and I hope it was useful. Any suggestions or improvements are welcome.

The nice images above were made with Desmos.

If you want other links/problems on CHT to be added, comment below and I will add them.

Great tutorial! Another good resource for those who prefer to learn from videos is Algorithms Live — Convex Hull Optimization.

I've added the link. One thing that irked me, in the first part the author says that (

x-y)^{2}+prevCostis not really CHT because the functions are parabolic and not straight lines, but the expression can be expanded toy^{2}- 2xy+x^{2}+prevCostwhich needs to be minimized for fixedyover somex, so it actually can be solved in the normal way with a convex hull of lines.I think PDELIV deserves a mention in the problem list. It requires you to use it in a way I personally hadn't considered before.

Nice problem, added to the list!

I like the implementation created by simonlindholm, found in the KTH notebook. I originally saw ksun48 use it here: https://codeforces.com/contest/1083/submission/46863810.

You can find it in here:https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/LineContainer.h

I think it's a lot less magic than the other 2 implementations linked (no mutable member functions/closures), and I believe it's also substantially faster.

This implementation appears short and neat. Added to the blog. Have you also compared the performance?

The primary thing that differentiates this implementation is that it stores the intersection point during insertion. This makes the implementation a lot shorter as well as the queries somewhat faster. Overall, compared to the other 2 implementations linked (called HullDynamic and chtDynamic respectively), it's somewhat slower at insertion than the other two, significantly faster at querying than HullDynamic, and slightly faster at querying than chtDynamic. Overall, it's very competitive in performance.

Insertions (1e7 insertions)

Queries (1e5 insertions, 1e7 queries)

Overall (1e7 insertions, 1e7 queries)

And finally, line count :^)

I think the KTH implementation is clearly the winner. Benchmarks can be found here: https://ideone.com/caYDdF

Starting with C++14,

`std::less<void>`

is transparent, so you don't even need the hack with the global bool Q. Instead, you can use different`operator<`

for lines and query points. submissionOh, that's nice. Is there any reason you made p mutable?

p is the x-coordinate of the intersection with the next line and you need to update that when inserting new lines. A line inside the set is const, so you need mutable to make p modifiable. (k and m don't need to be changed, so they're not mutable.)

Oh, neat! I've made that change to KACTL: https://github.com/kth-competitive-programming/kactl/commit/165807e28402c9be906f6e6a09452431787bb70d

Is it possible to remove lines from the struct?

You can technically remove lines from the structure, but you cannot bring back the lines you previously discarded for the purpose on maintaining only the hull instead of all lines.

One or more of those discarded lines may have the second largest value at some $$$x$$$ where the removed line had the max value, which you cannot recover. So you will be having an incomplete hull.

Yeah, that makes sense. So is there any other way which allows remove or update queries on the line parameters while maintaining the complete hull?

Not that I know of, assuming you want to keep the same or close enough complexity.

If queries is offline I think Divide & Conquer O(n * log^2) helps like in Dynamic Connectivity (easy google). Online harder, idk maybe some kind of SQRT decomposition on queries. Smth like keep last B queries and proceed in stupid way, for other queries there is built CHT. So number of stupid asks will be B * q, number of CHT rebuilds will be q / B. To avoid sorting we can merge, so if B = sqrt(n), and for simplicity q = n. Complexity is O(n * sqrt(n) + q * log(n))

You can do it using treap

Why do you need this 'while' in add function?

I deleted it and got AC. Maybe it's useful for different problems?

I guess it's perhaps unnecessary when the lines you're adding are increasing in some manner? KACTL's stress tests fail without those two lines, though, so in general they are necessary.

How do I make it query the minimum value instead of the maximum? I'm just starting to learn this, so sorry for the dumb question.

Edit: I figured it out, you're supposed to insert the negatives.

Here's another related problem: YATP.

Nice problem. If anyone needs hints...

SpoilerCentroid decomposition.

Further explanation in this video: Algorithms Live — YATP w/ Lewin Gan

Great Tutorial!!!

This problem POLY can also be added here.

Thanks, updated.

Also, Lena and Queries

Great Tutorial! I tried solving the problem 1083E - Орехус и прямоугольники but for some reason my code is giving WA on test 5. Can someone please help me. 57194241

You're forcibly including the first rectangle always. The optimal solution might leave it out.

Fix is that when in

`ll m = get_max(lines, v[i].q);`

you find`m < 0`

you should not add it to`dp[i]`

.How do I modify the data structure so it gets the minimum at a point instead of the maximum?

Edit: I figured it out, you should insert the negatives of the slopes and constants.

which order of the slopes or queries are relevant? decreasing or increasing. Or both? I'll be appreciated if you answer this comment :3

The only difference between my AC code 69191641 and my WA on test 6 code for problem E — The Fair Nut and Rectangles was the "long double" used for comparing in fuction

`check()`

, which i put there because I saw that in many other's code. However, I didn't used any division, and the problem statement clearly said that xi, yi, ai are all int, so I'm very confused. Can someone please explain ?$$$b$$$ can be up to $$$10^{18}$$$ and $$$m$$$ can be up to $$$10^6$$$, so this multiplication overflows 64bit integers.

can some please tell me how to solve this problem https://codeforces.com/contest/319/problem/C using li chao tree....

In the implementation of "A More General Problem", how are you using lower bound for deque. You are doing lower bound for vector but in comparator using deque. I am not getting it. Can you explain it or share some links from where I can read about it? meooow.

Thank You

The vector has integers $$$0, 1, 2, 3, 4, ...$$$ so this is just a clever way to not code his own binary search to find the index of the optimum line for a particular $$$x$$$.

It would be a bit tricky to use lower_bound over the deque because we have to find the intersection with the next line. To do it you can keep the intersection with the next line in the struct and update it on insert.

Thank you for answering it.

I got it for deque.

How will we write lower bound for a set (In Full Dynamic Version) for query part? Nson

Here is the kactl version

The $$$p$$$ in the line struct represents the $$$x$$$ coordinate of the intersection with the next line. You can see it is modified upon insertion. This way you can do the same lower_bound without knowing the next line.

Got it. Thank you.

Nson is correct, it is just to avoid writing binary search code.

The

`lower_bound`

does the binary search job and calculates the smallest`idx`

for which`dq[idx]`

and`dq[idx + 1]`

intersect at x-position`>= a[i].q`

.Got it.Thank you.

Hi, was looking at the Li Chao tree method and it seems a lot simpler. Would just like to know, does Li Chao tree have any limitations? Is it possible to use it even in a non-dynamic version (lines are sorted by slope, query not arbitrary)?

Yes, if it works as fully dynamic, that means you can insert and query in any order. That includes sorted order.

Limitations of Li Chao tree that I can think of are (1) it only supports integer queries, and

(2) operations take logarithmic time with respect to the query domain size rather than the current size of the hull.

Ah, I see. Thank you so much :D

Isn't it possible to use coordinate compression with Li Chao? If yes, then both issues go away. (I think so, not really sure).

Hi. Can anyone help my with problem Avoiding airports?

My main idea: For every outgoing edge u->v (s,e) find the min cost that we can reach v at time e:

From all incoming edges into u, earlier than s, find the min:

F(v,e) = min{e_i < s}(F(u, e_i) + (s — e_i) ^ 2) = s^2 + min(F(u,e_i) + e_i ^ 2 — 2 * e_i * s)

This is standard CHT. For every vertex I keep CHT and process time points:

1) if at time T I have outgoing edge from u to v (T, T2) — I say add to CHT[v] at time T2 line (-2*T2, Query(CHT[u], T) + T2^2)

2) if at time T I have incoming edge (e.g. the promise from step 1): I just added that line to CHT of a given vertex.

See my code: https://pastebin.com/RPnrHGJ0

It fails on test 5, where 50 < n < 100, m ~200000, and there is at least one pair (u,v) with the same departure and landing time (s = e)

Any ideas?

I found the solution with LiChao tree that is very similar to mine. Can anyone explain why LiChao is needed?