线段树 (区间查询)维基百科,自由的 encyclopedia 线段树是一种二叉树,可视为树状数组的变种,最早出现在2001年,由算法竞赛选手发明。 关于用以存储区间或线段的数据结构(区间树),请见“线段树 (存储区间)”。 此条目可能包含原创研究。 (2017年3月10日) 此条目需要补充更多来源。 (2017年3月10日) 此数据结构实际应用用途不大,但由于其程序易于实现而被广泛应用于算法竞赛当中。其用途是在 O ( log N ) {\displaystyle O(\log N)} 查询一个指定区间内的资讯,并可在同样的时间复杂度支持更新等操作。
线段树是一种二叉树,可视为树状数组的变种,最早出现在2001年,由算法竞赛选手发明。 关于用以存储区间或线段的数据结构(区间树),请见“线段树 (存储区间)”。 此条目可能包含原创研究。 (2017年3月10日) 此条目需要补充更多来源。 (2017年3月10日) 此数据结构实际应用用途不大,但由于其程序易于实现而被广泛应用于算法竞赛当中。其用途是在 O ( log N ) {\displaystyle O(\log N)} 查询一个指定区间内的资讯,并可在同样的时间复杂度支持更新等操作。