ToB企服应用市场:ToB评测及商务社交产业平台
标题:
线段树
[打印本页]
作者:
小小小幸运
时间:
2024-2-19 05:00
标题:
线段树
线段树
什么是线段树
线段树
（英语：Segment tree）是一种
二叉树
形数据结构，1977年由Jon Louis Bentley发明[
1]
，用以存储
区间
或
线段
，并且允许快速查询结构内包含某一点的所有区间。
一个包含n个区间的线段树，空间复杂度为O(n)，查询的时间复杂度则为O(logn+k)},其中k是匹配条件的区间数量。
此数据结构亦可推广到高维度。
摘自
《维基百科》
为什么要使用线段树
线段树的时间复杂度分析：
线段树基础表示
如果区间有n个元素，用数组表示线段树，需要多少结点？
0层：1
1层：2
2层：4
3层：8
...
h-1层：2^(h-1)
对于满二叉树：
h层，一共有2h-1个结点（约为2h）
最后一层(h-1)，有2^(h-1)个结点
最后一层的结点数大致等于前面所有层的结点数之和
由此，可得出结论，我们线段树不考虑添加元素，即区间固定，使用4*n的静态空间即可。
public class SegmentTree<E> {
private E[] tree;
private E[] data;
public SegmentTree(E[] arr){
data=(E[])new Object[arr.length];
for(int i=0;i<arr.length;i++){
data[i]=arr[i];
}
tree=(E[])new Object[4*arr.length];
}
public int getSize(){
return data.length;
}
public E get(int index){
if(index<0 || index>=data.length){
throw new IllegalArgumentException("Index is illegal");
}
return data[index];
}
//返回完全二叉树的数组表示，一个索引所表示的元素的左孩子结点的索引
public int leftChild(int index){
return 2*index+1;
}
//返回完全二叉树的数组表示，一个索引所表示的元素的右孩子结点的索引
public int rightChild(int index){
return 2*index+2;
}
}
复制代码
本文由博客一文多发平台
OpenWrite
发布！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)
Powered by Discuz! X3.4
线段树的时间复杂度分析：
线段树基础表示
如果区间有n个元素，用数组表示线段树，需要多少结点？
由此，可得出结论，我们线段树不考虑添加元素，即区间固定，使用4*n的静态空间即可。