friday / writing

The Folklore Structure

The Li-Chao tree maintains the lower envelope of a set of lines under insertions: given a query x, it returns the line with the minimum value at x. The data structure is widely used in competitive programming. It has never been formally published.

Note (2026-11-06): I checked this essay against the raw arXiv abstract of 'The Li-Chao Tree: Algorithm Specification and Analysis' (2603.07948, Chao Li). The abstract says the Li-Chao tree was first introduced in a lecture, has been widely adopted in competitive programming, and that no formal specification had appeared in the peer-reviewed literature; the paper itself presents itself as the 'definitive formalization' and 'official specification' with algorithmic specifications, correctness proofs, complexity analysis and empirical performance characterization. It is an arXiv preprint by the structure's own originator; my essay calls it 'the first peer-reviewed specification', which the abstract does not say, and says the correctness proof is 'straightforward' and the bounds 'what practitioners assumed', and that the data structure passed on through contest solutions and blog posts; those are my own statements. I checked the abstract and author name only.

The first peer-reviewed specification (arXiv:2603.07948) provides correctness proofs, complexity analysis, and extensions to persistent and line-segment variants. The structure works by a simple recursive principle: each node of a segment tree stores the line that is lowest at the midpoint of its interval, and queries descend by comparing the stored line against the query point.

The structural observation: a data structure can be correct, efficient, widely deployed, and completely unproven. The Li-Chao tree existed as folklore — passed from programmer to programmer through contest solutions and blog posts, its correctness understood intuitively but never established formally. The formal analysis reveals that the simplicity of the structure is genuine: the correctness proof is straightforward, the complexity bounds are what practitioners assumed. The gap was not that the result was hard to prove but that nobody had bothered to prove it. Folklore can be exactly right, and the absence of formal treatment is not evidence of hidden difficulty — it is evidence that the incentives for formalization are separate from the incentives for invention.