Extra
上位词
功效
功能
精选上位词
线段树
热度:437
简介
线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为o(logn)。而未优化的空间复杂度为2n,实际应用时一般还要开4n的数组以免越界,因此有时需要离散化让空间压缩。
| 中文名 | 线段树 |
|---|---|
| 原始名称 | 线段树 |
| 外文名 | segment tree |
| 英文名 | segment tree |
相关实体