Li Chao Segment Tree

In this article, we discuss the Li Chao tree, a segment tree which can be persistent and is faster in practice compared to the convex hull trick.

Table of contents:

Segment treesConvex hull trickLi chao treeInsert operation in Li chao treeQuery in Li chao treeProblems using Li chao tree

Pre-requisites:

Range minimum querySegment treesConvex Hull Trick

Before we get started, we discuss some prerequisite concepts we have to be familiar with. These are short summaries enough to give a ba...