线段树
线段树什么是线段树
线段树（英语：Segment tree）是一种二叉树形数据结构，1977年由Jon Louis Bentley发明[1]，用以存储区间或线段，并且允许快速查询结构内包含某一点的所有区间。
一个包含n个区间的线段树，空间复杂度为O(n)，查询的时间复杂度则为O(logn+k)},其中k是匹配条件的区间数量。
此数据结构亦可推广到高维度。
摘自《维基百科》
为什么要使用线段树
https://gitee.com/duhouan/ImagePro/raw/master/java-notes/dataStructure/segmentTree//segmentTree00.pnghttps://gitee.com/duhouan/ImagePro/raw/master/java-notes/dataStructure/segmentTree//segmentTree01.pnghttps://gitee.com/duhouan/ImagePro/raw/master/java-notes/dataStructure/segmentTree//segmentTree.png线段树的时间复杂度分析：
https://gitee.com/duhouan/ImagePro/raw/master/java-notes/dataStructure/segmentTree//segmentTree_2.pnghttps://gitee.com/duhouan/ImagePro/raw/master/java-notes/dataStructure/segmentTree//segmentTree_3.png线段树基础表示
https://gitee.com/duhouan/ImagePro/raw/master/java-notes/dataStructure/segmentTree//segmentTree_4.png如果区间有n个元素，用数组表示线段树，需要多少结点？
0层：1
1层：2
2层：4
3层：8
...
h-1层：2^(h-1)
对于满二叉树：
h层，一共有2h-1个结点（约为2h）
最后一层(h-1)，有2^(h-1)个结点
最后一层的结点数大致等于前面所有层的结点数之和
https://gitee.com/duhouan/ImagePro/raw/master/java-notes/dataStructure/segmentTree//segmentTree_5.png由此，可得出结论，我们线段树不考虑添加元素，即区间固定，使用4*n的静态空间即可。
public class SegmentTree<E> {
private E[] tree;
private E[] data;
public SegmentTree(E[] arr){
data=(E[])new Object;
for(int i=0;i<arr.length;i++){
data=arr;
}
tree=(E[])new Object;
}
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;
}
//返回完全二叉树的数组表示，一个索引所表示的元素的左孩子结点的索引
public int leftChild(int index){
return 2*index+1;
}
//返回完全二叉树的数组表示，一个索引所表示的元素的右孩子结点的索引
public int rightChild(int index){
return 2*index+2;
}
}本文由博客一文多发平台 OpenWrite 发布！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]