The Li-Chao Tree: Algorithm Specification and Analysis

Chao Li · 2026

Read The Li-Chao Tree: Algorithm Specification and Analysis by Chao Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-07948.txt.

Description

Li gives the Li-Chao tree its first formal account in journals, closing a gap for a data structure that has spread widely through competitive programming since its debut in lecture. The tree maintains the dynamic lower envelope of lines fast, yet until now it lived only in lecture notes and lore. It covers details, correctness proofs, complexity analysis, and measured speed tests. Li highlights strengths in coding simplicity, numerical stability, and extensibility to variants such as persistence and line segments.

Catalog record

CREATORChao Li
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28751
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.07948

Browse the full library · About the Tower of Babel