线段树

它是一种怎样的数据结构

假设一个数组[1,2,3,4,5,6]，它是一个[0,5]的数组，如果要求它的各个区间合[i,j]，那么每次查询一个区间都需要将i加到j，总的来说区间和的复杂度为O(n)；而更新位置的值，则需要O(1)的复杂度。
线段树将数组通过二分分割成一系列区间，将区间和以及修改的复杂度变成O(logn)

线段树.png

通过下面这段代码可以构造一个线段树

1.通过2*i+1，2*i+2分别拿到左右子节点
2.将原数组通过区间映射到线段树上，左子区间为左子节点，右子区间为右子节点
3.当区间缩减为一个整数时候，节点上的值就是次整数的值
4.在宏观上，当前节点的值等于左子节点加上右子节点

    int[] segmentTree ;
    int[] nums;
    private void buildTree(int cur,int start,int end){
        if(start >= end){
            segmentTree[cur] = nums.length>0?nums[start]:0;
        }else {
            int mid = start + ((end-start)>>1);
            int left = (cur<<1) + 1;
            int right = (cur<<1) + 2;
            buildTree(left,start,mid);
            buildTree(right,mid+1,end);
            segmentTree[cur] = segmentTree[left] + segmentTree[right];
        }
    }

区间更新

线段树1.png

1.通过二分查找定位i的位置，start与end为区间广度，在区间中定位出i的位置
2.同时计算线段树对应的节点，比如[start,end]为节点0，[mid+1,end]为节点2

    private void update(int cur,int start,int end,int i,int val){
        if(start == end){
            nums[start] = val;
            segmentTree[cur] = val;
        }else {
            int mid = start + ((end-start)>>1);
            int left = (cur<<1) + 1;
            int right = (cur<<1) + 2;
            if(i > mid){
                update(right,mid+1,end,i,val);
            }else {
                update(left,start,mid,i,val);
            }
            segmentTree[cur] = segmentTree[left] + segmentTree[right];
        }
    }

区间和

1.求和的基本思路是节点的值为左右子节点的和
2.当[i,j]与[start,end]不存在交集的时候，返回0
3.当[i,j]在区间[start,end]内的时候，返回当前节点的值

    private int sumRange(int cur,int start,int end,int i,int j){
        if(start > j || end < i){
            return 0;
        }else if(start >= i && end <= j){
            return segmentTree[cur];
        }else {
            int mid = start + ((end-start)>>1);
            int left = (cur<<1) + 1;
            int right = (cur<<1) + 2;
            return sumRange(left,start,mid,i,j)+sumRange(right,mid+1,end,i,j);
        }
    }

简单分析

一个n长度的数组，构造线段树数组需要4*n+1
递归深度是log（4n+1）