SegmentTree的历史

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.

Share