线段树 Segment Tree--数据结构Summary(一）

线段树

线段树是一种二叉搜索树，将一个区间划分成细小的单元区间。每个区间对应线段树中的一个叶子结点。每个非叶子结点都有左右两颗子树。一般我们按照从上到下、从左到右的顺序给所有结点进行编号为1，2，3....对于任意编号为 i 的结点 ,若它表示的范围为[a,b]，则它的左右子结点编号分别为2i、2i+1，左右子结表示的区间范围分别为[a,(a+b)/2]，[(a+b)/2+1,b]。因此线段树也为一颗平衡二叉树。

 线段树可以快速的查找某一个结点出现的次数，其复杂度为O（logN），未优化的空间复杂度为 2N。是一种用空间换取时间的数据结构。

建树