How prefix-sum binary search makes text line-breaking O(log n) with zero allocation

Most text layout implementations find line breaks by scanning forward character by character, accumulating widths until they exceed the container. That's O(n) per line and it allocates intermediate results along the way. There's a better approach using prefix sums and binary search. I used it in a text layout engine I built called ZeroText, and the technique is general enough to be useful anywhere you need to partition a sequence by cumulative weight. The naive approach let x = 0; for (let i = start; i < text.length; i++) { x += getWidth(text[i]); if (x > containerWidth) { // break at i-1, start new line break; } } This is O(n) per line. For a 10,000-character document with 500 lines, you're touching every character at least once per layout. And getWidth might itself allocate — Canvas measureText returns a new TextMetrics object every call. DOM-based measurement triggers synchronous reflow. Prefix sums turn range queries into subtraction Compute the prefix sum array in a single p