Segmented winner trees
Andrew E. B. Lim, Sartaj K. Sahni · 1992
A new data structure, "segmented winner tree", is introduced. This is useful when one needs to represent data that are partitioned into segments. The segment operations that are efficiently supported are: initialize a unit length segment, find the element with least value in any given segment, update an element in any segment, merge two adjacent segments, and split a segment.