线段树

维基百科,自由的百科全书
跳转至: 导航搜索

线段树Segment Tree)是一种二叉搜索树,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点

对于线段树中的每一个非叶子节点[a,b],它的左子树表示的区间为[a,(a+b)/2],右子树表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树。叶节点数目为N,即整个线段区间的长度。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。

给定整个线段区间,建立一棵线段树的时间复杂度是 O(N)。单点修改的时间复杂度是 O(log N)。单点查询的时间复杂度是 O(1)。如果允許惰性賦值而加上延遲標記的話,許多的區間修改的時間複雜度也會是 O(log N),但是单点查询的时间复杂度会变成 O(log N)。

另外还有如zkw线段树的特种线段树。

相关链接:http://dongxicheng.org/structure/segment-tree/