Latest / Deep End Era. Engineering with Sankalp
Remember the Furthest End: Segment Trees, Fenwick Trees and Interval Trees
In Singapore, intern Tomás Ferreira finds a dashboard doing ten billion additions a second and a genome job that takes nine hours. In part fourteen of The Deep End's Data Structures series, genomics engineer Mei Lin Tan shows him three trees that answer questions about ranges. We build a segment tree like a tournament bracket, find a tree hiding inside binary numbers thanks to a 1994 compression paper, and learn why remembering the furthest end of every interval lets you skip almost everything. Plus the off-by-one convention that haunts genomics. Mei Lin and Tomás are fictional; the…
The skinny
The skinny isn't ready yet — notes appear once the transcript is processed.