SeqTree

线段树

需要清楚的几个概念:完全二叉树、二叉树的二叉链表表示法

首先以二叉链表表示的完全二叉树使用数组存储的时候是具有一定规律的:

比如: 当某子树的根节点的索引为i是,其左子树根节点的索引是 2*i+1

而右子树的根节点的索引是2*i+2,从下面的代码里我们就可以看见使用以上公式的递归方式

线段树的定义

线段树,类似区间树,各个节点代表着某一个区间的最小值(最大值),注意是区间。主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(logn)。

长度为6的数组arr [2,5,1,4,9,3] 元素索引范围为 [0,5] 中间索引为2

所以第一次划分区间为:[0,2] 、[3,5], 构建根节点,根节点的值是两个区间的最小或者最大值,[0,2] 为此根节点的左子树,[3,5] 为此根节点的右子树。

接下来划分[0,2]区间 (0+2)/2=1,中间索引是1 ,经过划分成为: [0,1]、[2,2],此时[2,2] 就是一个叶子节点代表着数组中的某一个数字,然后直接赋值。

….依次类推

以上是如何构建一颗线段树,代码简单易懂,只要把握住完全二叉树、二叉树二叉链表表示法的特征便可。

查询线段树:查询某区间的最小(最大)值

参数是 目标区间[qstart,qend]

我们当然是从线段树的根节点进行查询,此时是起始区间[0,nums.length-1] (num是目标数组)

线段树平分为左右子树,考察此时所代表的区间是否与目标区间有交集,如果有交集,继续划分,如果目标区间包含此时的区间,那么就找到了此子树的最小(最大值)。如果无交集,则返回Integer.MAX_VALUE。

左右子树返回的值取较小值….

总的来说两个字:递归

单点更新/区间更新,未完待续…..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
public class SeqTree {
private Integer length=100;
private SeqTreeNode[] seqTreeNodes=new SeqTreeNode[this.length];
private int [] nums;
private int numsLength;
public SeqTree(int length,int [] nums){
this.nums=nums;
numsLength=nums.length;
createSeqTree(0,nums,0,length-1); //构造线段树
}
static class SeqTreeNode{
Integer val;
int addMark; //延迟标记:更新区间节点而不是去更新叶子节点,称为延迟标记
SeqTreeNode(int val){
this.val=val;
}
}
//构建一颗线段树
private void createSeqTree(int root, int arr[], int istart, int iend){
if(iend==istart){ //叶子节点
seqTreeNodes[root]=new SeqTreeNode(arr[istart]);
}else{
int mid=(istart+iend)/2;
createSeqTree(root*2+1,arr,istart,mid); //左子树 2*root+1是因为线段树是一颗完全二叉树,所以寻找左子树的索引计算方式是 2*root+1
createSeqTree(root*2+2,arr,mid+1,iend); //右子树 寻找右子树的索引计算方式是 2*root+2
seqTreeNodes[root]=new SeqTreeNode(Math.min(seqTreeNodes[root*2+1].val, seqTreeNodes[root*2+2].val));
}
}
/*
* 每一颗子树的根节点代表着某一个区间的最小值
* root 代表线段树当前节点下标 初始为0
* [nstart,nend] 代表当前节点所表示的区间,初始值为 [0,length-1]
* [qstart,qend] 代表目标区间
* */
public int query(int root, int nstart, int nend, int qstart, int qend){
if(qstart > nend || qend < nstart) //目标区间与查询区间无交集
return Integer.MAX_VALUE;
if (qstart <= nstart && qend >= nend){ //查询区间在目标区间之间时,直接返回此时的根节点,需要注意的是[0,3]
return seqTreeNodes[root].val;
}
int mid=(nstart+nend)/2;
return Math.min(
query(root*2+1,nstart,mid,qstart,qend),
query(root*2+2,mid+1,nend,qstart,qend)
);
}
/*
* 线段树的单点更新,更新单点不就是更新叶子节点,所以问题转化成寻找叶子节点,而由线索树的特征可知,叶子节点所表示的区间是具体到某一个值
* 例如:数组索引为3的节点 指的是[3,3] 的最小值
* */
public void update(int root,int nstart, int nend, int index,int addval){
if (nstart==nend){
if (index==nstart){
seqTreeNodes[root].val+=addval;
}
return;
}
int mid=(nstart+nend)/2;
if (index<=mid){ //左子树更新
update(root*2+1, nstart, mid, index, addval);
}else { //右子树更新
update(root*2+2, mid+1, nend, index, addval);
}
//更新之后回溯更改根节点的值
seqTreeNodes[root].val=Math.min(seqTreeNodes[root*2+1].val,seqTreeNodes[root*2+2].val);
}


public static void main(String[] args) {
SeqTree seqTree= new SeqTree(6,new int[]{
2,5,1,4,9,3
});
System.out.println(seqTree.query(0,0,5,2,4));
}
}