1. 线段树入门

线段树，类似区间树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(logn)。

线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]。线段树形如：

下面我们从一个经典的例子来了解线段树，问题描述如下:从数组arr[0…n-1]中查找某个数组某个区间内的最大值，其中数组大小固定，但是数组中的元素的值可以随时更新。从这题可以看出：区间(a,b)的最大值和区间(b,c)的最大值中，取较大的就是区间(a,c)的最大值。很明显这个操作具有区间的性质。

我们可以用线段树来解决这个区间最大值问题。根据这个问题我们构造如下的二叉线段树。区间的第三维就是区间的最大值。

加入第三维的时候，只需要在构建完左右区间后，根据左右区间的最大值更新当前区间最大值即可。

因为每次将区间长度一分为二，所有构造的节点个数为：

n + 1/2 n + 1/4 n + 1/8 * n + …

= (1 + 1/2 + 1/4 + 1/8 + …) * n

= 2n

所以构造线段树的时空复杂度都为O(n)。

1.1. 线段树常见题型

一道题可不可以用线段树来做，基本是看这道题的操作有没有区间的性质。也就是在一个区间上的操作是否可以转化为两个子区间上的操作。

求区间和，积，最小值，gcd等
以当前节点的值作为节点处理。例如给出N个数字，再给一个数，问比这个数大的有多少个。
区间加减同一个值，或者区间同时赋一个值。

1.2. 链式线段树

我们常见的二叉树都是链式结构。因此我们先完成链式的线段树。

建树

复杂度O(n)

public class SegmentTree {
    //线段树节点定义
    public class SegmentTreeNode{
        int start;
        int end;
        int max;
        SegmentTreeNode left = null;//定义左右节点
        SegmentTreeNode right = null;
        SegmentTreeNode(int start,int end,int max){
            this.start = start;
            this.end = end;
            this.max = max;
        }
    }
    public SegmentTreeNode builder(int[] A){
        return helper(0,A.length-1,A);
    }
    public SegmentTreeNode helper(int low,int high,int[] A){
        if (low > high){
            return null;
        }
        SegmentTreeNode root = new SegmentTreeNode(low,high,A[low]);
        if(low == high){
            return root;
        }
        else{
            root.left = helper(low,high/2,A);
            root.left = helper(high/2+1,high,A);
            root.max = Math.max(root.left.max,root.right.max);//更新当前节点max值
        }
        return root;
    }
}

区间查询

复杂度 O(log(n))O(log(n))

构造线段树目的是为了更快地查询。例如给定区间，要求区间中的最大值。而线段树的区间查询操作就是将当前区间分解为较小的子区间，然后由子区间的最大值就可以快速得到需要查询区间的最大值。例如

query(1,3) = max(query(1,1), query(2,3)) = max(4,3) = 4

查询实现：

//在线段树中查找[low,high]区间的最大值
public int query(SegmentTreeNode root,int low,int high){
    if(root.start == low && root.end == high){
        return root.max;
    }
    int mid = (root.start + root.end) / 2;
    int result = Integer.MIN_VALUE;
    if(mid >= low){//查询区间与左半区间有交集，最大值有可能在左半区间
        result = Math.max(result,query(root.left,low,mid));
    }
    if(mid+1 <= high){ //查询区间与右半区间有交集，最大值有可能在右半区间
        result = Math.max(result,query(root.right,mid+1,high));
    }
    return result;
}

单点更新

复杂度 O(log(n))O(log(n))

更新序列中的一个节点，那么如何把这种变化体现到线段树中呢？

例如要将第4个点更新为5.就要变动3个区间的值，分别为[3,3], [2,3], [0,3]

改动一个节点，与这个节点对应的叶子结点都要变动。并且，这个节点变动后，这个节点的属性值也有可能会变动，那么就有可能影响到这个节点的父亲节点的属性值（例如可能影响到最大值）。所以需要从叶子节点一路走到根节点。

单点更新实现：

public void modify(SegmentTreeNode root,int idx,int val){
    ////如果找到相应叶子节点了
    if(root.start == root.end && root.start == idx){
        root.max = val;//修改max值
        return;
    }
    int mid = (root.start + root.end) / 2;
    if(idx <= mid){//要修改的在左边
        modify(root.left,idx,val);
    }
    else {
        modify(root.right,idx,val);
    }
    //跟新root的max
    root.max = Math.max(root.left.max,root.right.max);
}