線段樹

它是一種怎樣的數(shù)據(jù)結(jié)構(gòu)

假設(shè)一個數(shù)組[1,2,3,4,5,6]浦旱，它是一個[0,5]的數(shù)組诗越，如果要求它的各個區(qū)間合[i,j]厘熟，那么每次查詢一個區(qū)間都需要將i加到j(luò)，總的來說區(qū)間和的復(fù)雜度為O(n)嘀趟；而更新位置的值脐区，則需要O(1)的復(fù)雜度。
線段樹將數(shù)組通過二分分割成一系列區(qū)間她按，將區(qū)間和以及修改的復(fù)雜度變成O(logn)

線段樹.png

通過下面這段代碼可以構(gòu)造一個線段樹

1.通過2*i+1牛隅，2*i+2分別拿到左右子節(jié)點
2.將原數(shù)組通過區(qū)間映射到線段樹上炕柔，左子區(qū)間為左子節(jié)點，右子區(qū)間為右子節(jié)點
3.當(dāng)區(qū)間縮減為一個整數(shù)時候媒佣，節(jié)點上的值就是次整數(shù)的值
4.在宏觀上匕累，當(dāng)前節(jié)點的值等于左子節(jié)點加上右子節(jié)點

    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];
        }
    }

區(qū)間更新

線段樹1.png

1.通過二分查找定位i的位置，start與end為區(qū)間廣度默伍，在區(qū)間中定位出i的位置
2.同時計算線段樹對應(yīng)的節(jié)點欢嘿，比如[start,end]為節(jié)點0，[mid+1,end]為節(jié)點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];
        }
    }

區(qū)間和

1.求和的基本思路是節(jié)點的值為左右子節(jié)點的和
2.當(dāng)[i,j]與[start,end]不存在交集的時候巡验，返回0
3.當(dāng)[i,j]在區(qū)間[start,end]內(nèi)的時候际插，返回當(dāng)前節(jié)點的值

    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長度的數(shù)組，構(gòu)造線段樹數(shù)組需要4*n+1
遞歸深度是log（4n+1）