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.

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.

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:

1. We'll keep the lines of the hull, in sorted order of slope.
2. We iterate over the rectangles from i = 1 to n, and p_i < p_j, q_i > q_j for i < j.
3. 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.
4. 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.

struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};

deque<line> dq;
dq.push_front({0, 0});
long long ans = 0;
for (int i = 1; i <= n; i++) {
    while (dq.size() >= 2 && dq.back().eval(rects[i].q) <= dq[dq.size() - 2].eval(rects[i].q))
        dq.pop_back();
    long long f = dq.back().eval(rects[i].q) + rects[i].p * 1LL * rects[i].q - rects[i].a;
    ans = max(ans, f);
    line cur = {-rects[i].p, f};
    while (dq.size() >= 2 && cur.intersectX(dq[0]) >= dq[0].intersectX(dq[1]))
        dq.pop_front();
    dq.push_front(cur);
}

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.

deque<line> dq;
vector<int> ints(n);
iota(ints.begin(), ints.end(), 0);
auto cmp = [&dq](int idx, int x) { return dq[idx].intersectX(dq[idx + 1]) < x; };
dq.push_front({0, 0});
long long ans = 0;
for (int i = 1; i <= n; i++) {
    int idx = *lower_bound(ints.begin(), ints.begin() + dq.size() - 1, a[i].q, cmp);
    long long f = dq[idx].eval(rects[i].q) + rects[i].p * 1LL * rects[i].q - rects[i].a;
    ans = max(ans, f);
    line cur = {-rects[i].p, f};
    while (dq.size() >= 2 && cur.intersectX(dq[0]) >= dq[0].intersectX(dq[1]))
        dq.pop_front();
    dq.push_front(cur);
}

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.