SegmentTree的历史

卡内基梅隆大学的 Bentley 撰写了 Algorithms for Klee’s rectangle problems，未发表，
Bentley 本人在 1980 年发表的 An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles，引用了 1977 的文章，可以认为是首次提出线段树的论文。o

Union-Copy Structures and Dynamic Segment Trees-1993-Kreveld
A New Data Structure for Cumulative Frequency Tables-1994-Fenwick

《Computational+Geometry+-+Algorithms+and+Applications,+3rd+Ed》 在 Chapter 10 收录了 Interval Tree 和 Segment Tree

Zingaro《Algorithmic Thinking》有介绍，线段树的其它名字：interval trees,tournament trees, order-statistic trees, and range query trees.