oneDay

1. 为什么要使用线段树
   因为对于某一类问题，我们关心的就只是线段（区间）
2. 线段树的一些经典问题
   区间染色问题：对于给定的一段区间，经过m次染色后，问区间[i,j]的颜色的种类（0=<i,j<=n-1）
   区间查询问题：查询在一段时间[i,j]区间内的要查询数据的动态情况
   对于这两个问题，使用数组也是可以解决的，但是时间复杂度为O(n)，而使用线段树的时间复杂度为O(logn)
3. 线段树的基本操作

• 更新：更新区间中的一个元素或者一个区间的值
• 查询：查询一个区间[i,j]内元素的最大值，最小值，或者区间数字的和

4. 线段树的结构

   
   捕获.PNG
   

   可以看到这个线段树是一个满二叉树，但是线段树不一定是满二叉树或者是完全二叉树，但它是一个平衡二叉树，也就是数中最大的高度和最小的高度的差小于等于1

5. 线段树的底层实现

• 这里使用数组来实现二叉树，首先先来分析一下对于给定的区间，数组的大小应该是多少（注意：这里将线段树统一视为满二叉树，也就是对于空位置的节点设为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

6. 线段树的创建
   线段树的创建使用了递归的方法，因为由线段树的结构可以知道，根节点的值就是两个子节点值的合并（这里合并可以是加，减等一系列的操作）,在创建这棵线段树的时候，就先创建它的左右的孩子，然后合并它们的值就是根节点的值（这里在创建的时候，为了使得用户可以更改对某个区间的操作，创建了一个类似于Comparator的接口merge，使得在初始化线段树的时候，可以向其中放入对某个区间的操作）
7. 线段树的查询
   同样的，实现线段树的查询操作也是使用递归来完成的， 对于给定的区间，如果只出现在右边，那就只需要在右边查询，如果只出现在左边，那就只需要在左边查询，但是如果即出现在左边，又出现在右边，那就要在左右查询，最后将左右的结果合并就是最后的结果 。

threeDay

8. 线段树的更新操作
   给定一个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)，我们来看一下树状数组的两种操作

1. query(int x) 指的是数组中[1,x]的所有元素的和

int res=0;
while x>0:
    res+=nums[x];
    x-=lowbit(x);

2. 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);
    }
}