oneDay
- 为什么要使用线段树
因为对于某一类问题，我们关心的就只是线段（区间） - 线段树的一些经典问题
区间染色问题：对于给定的一段区间，经过m次染色后，问区间[i,j]的颜色的种类（0=<i,j<=n-1）
区间查询问题：查询在一段时间[i,j]区间内的要查询数据的动态情况
对于这两个问题，使用数组也是可以解决的，但是时间复杂度为O(n)，而使用线段树的时间复杂度为O(logn) - 线段树的基本操作
- 更新：更新区间中的一个元素或者一个区间的值
- 查询：查询一个区间[i,j]内元素的最大值，最小值，或者区间数字的和
-
线段树的结构
捕获.PNG
可以看到这个线段树是一个满二叉树，但是线段树不一定是满二叉树或者是完全二叉树，但它是一个平衡二叉树，也就是数中最大的高度和最小的高度的差小于等于1
- 线段树的底层实现
- 这里使用数组来实现二叉树，首先先来分析一下对于给定的区间，数组的大小应该是多少（注意：这里将线段树统一视为满二叉树，也就是对于空位置的节点设为null就好了）
对于一棵满二叉树，每一层节点的个数与层数之间的关系为2^(n-1),其中最后一层的节点个数为2^(h-1),由于满二叉树的所有的节点个数为2^(h)-1,也就近似等于2^h,所以可以发现最后一层的节点的个数近似等于总结点数的一半，而最后一层的节点个数在当给定的区间的个数为n=2^k时，此时的n就是最后一层的节点的个数，所以总结点个数为2n，而如果n=2^k+1,这个时候n比最后一层的节点个数要多，也就是这个满二叉树要增加一层，而这一层上面的所有层的节点个数为2n，这一层也为2n，所以总共需要4n大小的数组来存储线段树，n代表的就是区间内元素的个数
综上，使用数组来实现线段树需要4*n大小的空间（n为区间内元素的个数） - 线段树没有添加元素的操作，区间是固定的，使用4*n的静态空间就好了
twoDay
- 线段树的创建
线段树的创建使用了递归的方法，因为由线段树的结构可以知道，根节点的值就是两个子节点值的合并（这里合并可以是加，减等一系列的操作）,在创建这棵线段树的时候，就先创建它的左右的孩子，然后合并它们的值就是根节点的值（这里在创建的时候，为了使得用户可以更改对某个区间的操作，创建了一个类似于Comparator的接口merge，使得在初始化线段树的时候，可以向其中放入对某个区间的操作） - 线段树的查询
同样的，实现线段树的查询操作也是使用递归来完成的， 对于给定的区间，如果只出现在右边，那就只需要在右边查询，如果只出现在左边，那就只需要在左边查询，但是如果即出现在左边，又出现在右边，那就要在左右查询，最后将左右的结果合并就是最后的结果 。
threeDay
- 线段树的更新操作
给定一个index和要更改为的值val，同样使用递归的方法，如果左右的边界相同了，说明这时候找到了index位置的这个点，那就更新线段树中的值，如果当前没有找到，就得到当前的线段树的顶点表示的区间的中点，如果index比中点大，就在右边找，如果比区间小，就在左边找，修改了左边或右边的值之后，对它们根节点的值也要更新，也就是对左右节点重新合并
到这里，线段树的所有的操作都已经完了，下面附上代码
- 对接口Merger的定义，它用于实现对区间的合并操作
//用于实现两个区间的合并操作
public interface Merger<E> {
E merge(E a,E b);
}
- 对线段树的书写
//实现一个线段树
public class SegmentTree<E> {
//创建线段树
private E[]tree;
//这里添加一个data，赋值用户给出的区间
private E[]data;
//创建一个merge，用于实现两个区间的合并
private Merger<E> merge;
//实现构造函数，用户只需要给出一个区间
public SegmentTree(E[]arr,Merger<E> merge) {
this.merge=merge;
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];
//一个线段树的节点的个数是区间个数的四倍
//创建线段树,传入参数就是根节点的坐标，还有根节点表示的区间的范围
buildSegmentTree(0,0,data.length-1);
}
//实现线段树的创建操作
private void buildSegmentTree(int treeIndex,int l,int r) {
//这里创建这个线段树要使用递归的方法来创建
//设置基线条件
if(l==r) {
tree[treeIndex]=data[l];
return;
}//如果左右的边界相同，那么这个节点表示的区间的值就是data[l]的值
//否则的话，取构建这个节点的左边和右边
int leftTreeIndex=LeftChild(treeIndex);
int rightTreeIndex=RightChild(treeIndex);
//找到区间的中点，将区间分为两部分
int mid=l+(r-l)/2;
buildSegmentTree(leftTreeIndex, l, mid);
buildSegmentTree(rightTreeIndex, mid+1, r);
//左右的区间都创建完毕后，根节点的区间就是合并左右两个区间
tree[treeIndex]=merge.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
}
//实现线段树的查询操作
public E query(int queryL,int queryR) {
if(queryL<0||queryL>=data.length||queryR<0||queryR>=data.length) {
throw new IllegalArgumentException("the segment is illegal");
}//判断给定的区间的合法性
return query(0,0,data.length-1,queryL,queryR);
}
private E query(int treeIndex,int l,int r,int queryL,int queryR) {
//首先设立基线条件就是当要查找的区间等于目前的区间的话，直接返回这个区间对应的值就好了
if(queryL==l&&queryR==r) {
return tree[treeIndex];
}
//这里先获取左节点的位置和右节点的位置
int leftTreeIndex=LeftChild(treeIndex);
int rightTreeIndex=RightChild(treeIndex);
//获取区间的中点
int mid=l+(r-l)/2;
if(queryL>=mid+1) {
return query(rightTreeIndex, mid+1, r, queryL, queryR);
}//如果区间在右边，那就无须看左边了
else if(queryR<=mid) {
return query(leftTreeIndex, l, mid, queryL, queryR);
}//如果区间在左边，就无须看右边了
else {
//最后一种情况就是这个要查询的区间在左右子树都有
E leftValue=query(leftTreeIndex, l, mid, queryL, mid);//在左边找到queryL到mid的值
E rightValue=query(rightTreeIndex, mid+1,r,mid+1,queryR);//在右边找到mid+1到qureyR的值
return merge.merge(leftValue, rightValue);//将左右合并返回就好了
}
}
public void set(int index,E val) {
if(index<0||index>=data.length) {
throw new IllegalArgumentException("the index is illegal");
}
data[index]=val;
set(0,0,data.length-1,index,val);
}//将第index位置的元素变为val
private void set(int treeIndex,int l,int r,int index,E val) {
if(l==r) {
tree[treeIndex]=val;
return;
}//如果左右边界相等，证明这个时候只有一个元素，那就是index位置的元素
int mid=l+(r-l)/2;//获得区间中点的值
int leftIndex=LeftChild(treeIndex);//获取左孩子的位置
int rightIndex=RightChild(treeIndex);//获取右孩子的位置
if(index>=mid+1) {
set(rightIndex, mid+1,r,index,val);
}//如果index位置在右边，就去修改右边的值
else {
set(leftIndex, l,mid,index,val);
}//如果index位置在左边，就去左边修改值
tree[treeIndex]=merge.merge(tree[leftIndex], tree[rightIndex]);//最后更新根节点的值
}
private E get(int index) {
//获得某个位置的数据
if(index<0||index>data.length) {
throw new IllegalArgumentException("The index is nort legal");
}
return data[index];
}
private int getSize() {
//获取区间的大小
return data.length;
}
private int LeftChild(int index) {
//获取左孩子节点的位置
return 2*index+1;
}
private int RightChild(int index) {
//获取右孩子节点的位置
return 2*index+2;
}
@Override
public String toString() {
StringBuffer res=new StringBuffer();
res.append('[');
for(int i=0;i<tree.length;i++) {
res.append(tree[i]);
if(i!=tree.length-1) {
res.append(", ");
}
}
res.append(']');
return res.toString();
}
}
这里还有一种和线段树很相似的数据结构：树状数组，它也可以完成对于数组中某个区间的查询和更新的操作，但是实现起来比线段树要简单，其中要使用到lowbit思想，对于lowbit就是指的某个数字的最低位的1所对应的10进制数字，例如10的lowbit为2，它的求解方法也很简单，就是num&(-num)，我们来看一下树状数组的两种操作
- query(int x) 指的是数组中[1,x]的所有元素的和
int res=0;
while x>0:
res+=nums[x];
x-=lowbit(x);
- update(int x,int val) 指的是将某个位置的元素加val,实现的简略代码如下：
while x<=n:
nums[x]+=val;
x=x+lowbit(x);
对于树状数组，具体的实现代码如下：
public class FenwickTree {
public int[]tree;
public int[]data;
public int size;
//设置构造函数
public FenwickTree(int[] nums) {
int n=nums.length;
data=new int[n+1];
tree=new int[n+1];
this.size=n;
for(int i=1;i<=n;i++) {
data[i]=nums[i-1];
}
for(int i=1;i<=n;i++) {
this.update(i,nums[i-1]);
}
}
public void update(int x,int val) {
int n=this.size;
while(x<=n) {
this.tree[x]+=val;
x+=lowbit(x);
}
}
public int query(int x) {
int res=0;
while(x>0) {
res+=this.tree[x];
x-=lowbit(x);
}
return res;
}
private int lowbit(int num) {
return num&(-num);
}
}
