线段树

线段树

什么是线段树

线段树（英语：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的静态空间即可。

1. public class SegmentTree<E> {
2.     private E[] tree;
3.     private E[] data;
4.     public SegmentTree(E[] arr){
5.         data=(E[])new Object[arr.length];
6.         for(int i=0;i<arr.length;i++){
7.             data[i]=arr[i];
8.         }
9.         tree=(E[])new Object[4*arr.length];
10.     }
12.     public int getSize(){
13.         return data.length;
14.     }
16.     public E get(int index){
17.         if(index<0 || index>=data.length){
18.             throw new IllegalArgumentException("Index is illegal");
19.         }
20.         return data[index];
21.     }
23.     //返回完全二叉树的数组表示，一个索引所表示的元素的左孩子结点的索引
24.     public int leftChild(int index){
25.         return 2*index+1;
26.     }
28.     //返回完全二叉树的数组表示，一个索引所表示的元素的右孩子结点的索引
29.     public int rightChild(int index){
30.         return 2*index+2;
31.     }
32. }

复制代码

本文由博客一文多发平台 OpenWrite 发布！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！