I made a video on the Convex Hull Trick (a great dynamic programming optimization). I explain the general idea and how we can implement it/the idea behind using it when:
- Our slopes are monotonic and our query values are monotonic
- Our slopes are monotonic
I basically explain it through the last problem of the atcoder dp contest (links to everything are available in the video description) so this video also serves as an editorial for Frog 3.
I do recommend that you first read the description as this video does have prerequisites.
Here is the video:
Convex Hull Trick Video
You can read more about CHT here:
CP-Algorithms Convex Hull Trick and Li Chao Trees
I don’t go into dynamic CHT or Li Chao Trees but you can check the video description for a tutorial on Li Chao Trees by radoslav192 which is a great tutorial. I was easily able to learn how Li Chao Trees work from it.