线段树 (存储区间)树形数据结构 / 维基百科,自由的 encyclopedia 线段树(英语:Segment tree)是一种二叉树形数据结构,1977年由乔恩·本特利发明[1],用以存储区间或线段,并且允许快速查询结构内包含某一点的所有区间。 此条目需要编修,以确保文法、用词、语气、格式、标点等使用恰当。 (2021年10月30日) 关于用于查询数列信息的数据结构,请见“线段树 (区间查询)”。 一个包含 n {\displaystyle n} 个区间的线段树,空间复杂度为 O ( n ) {\displaystyle O(n)} ,查询的时间复杂度则为 O ( log n + k ) {\displaystyle O(\log n+k)} ,其中 k {\displaystyle k} 是符合条件的区间数量。 此数据结构亦可推广到高维度。
线段树(英语:Segment tree)是一种二叉树形数据结构,1977年由乔恩·本特利发明[1],用以存储区间或线段,并且允许快速查询结构内包含某一点的所有区间。 此条目需要编修,以确保文法、用词、语气、格式、标点等使用恰当。 (2021年10月30日) 关于用于查询数列信息的数据结构,请见“线段树 (区间查询)”。 一个包含 n {\displaystyle n} 个区间的线段树,空间复杂度为 O ( n ) {\displaystyle O(n)} ,查询的时间复杂度则为 O ( log n + k ) {\displaystyle O(\log n+k)} ,其中 k {\displaystyle k} 是符合条件的区间数量。 此数据结构亦可推广到高维度。