資料結構: 線段樹Segment Tree

💕寫博客的目的在于鞏固所學知識💕

💕為什么要有線段樹

有這樣一個場景：給你一個陣列nums

有兩個任務

1.將 nums[index]的值更新為 val;( 0 =< index < nums.length,val為隨機值）

2.計算子陣列 nums[left, right] 的總和（即，nums[left] + nums[left + 1], ..., nums[right]）

這兩個任務會執行若干次，執行的順序隨機，

對于第一個任務，我們可以利用陣列的隨機訪問能力，在時間復雜度O(1)的情況下就能完成，

但對于第二個任務，我們可以采取累加的方式，從nums[left]一直加到nums[right]，時間復雜度為O(n)，

那么問題來了，我們有沒有再次基礎上進一步的降低時間復雜度？

有！那就是線段樹，

線段樹的結構

根據上面的陣列我們構成出了這樣的樹，突然看可能覺得很懵，

我們先從葉子節點看起

可以看出葉子節點從左到右分別為陣列nums[index]的值

再看父節點

可以知道父節點為左右兩個子節點之和，則根節點則為整個陣列之和，

這個時候，如果要我們計算nums[3,7]子陣列之和，我們只需要對二叉樹進行遍歷，找到圖中的兩個節點即可，

💕構造線段樹

Talk is cheap. Show me the code.

在開始之前，首先要明白線段樹其實是一個數狀陣列

把樹的每層從左到右依次排序，

可以發現

左子節點 = 父節點 * 2 + 1；

右子節點 = 父節點 * 2 + 2；

填到陣列中就是

    /**
     * 構造線段樹
     * @param num   原陣列
     * @param tree  這里的線段樹其實是一個陣列
     * @param node  樹節點
     * @param start num的開始下標
     * @param end num的結束下標
     */
    private void buildTree(int[] num,int[] tree, int node, int start, int end){
        // 遞回的出口
        // 每次將陣列一分為二
        // 知道陣列中就剩下一個數
        // 即start == end
        if (start == end){
            tree[node] = num[start];
        }else{
            int mid = (start+end)/2;
            // 根據父節點的下標求出子節點的下標
            int left_tree = node*2 + 1;
            int right_tree = 2*node + 2;
            // 遞回呼叫
            buildTree(num,tree,left_tree,start,mid);
            buildTree(num, tree, right_tree, mid+1, end);
            // 父節點的值等于左右子節點值之和
            tree[node] = tree[left_tree]+tree[right_tree];
        }
    }

💕更新線段樹

此時nums[3] = 6，如果我們要把nums[3]改為10，線段樹要怎么修改呢？

先從父節點出發，找到nums[3]在線段樹中對應的位置，修改節點后，在把沿途經過的父節點進行修改，

    /**
     * todo : 更新線段樹
     * @param num
     * @param tree
     * @param node
     * @param start 開始的位置仍然為0 
     * @param end   結束的位置為nums的長度-1
     * @param index 要修改位置的下標
     * @param value 要修改的值
     */
    private void updateTree(int[] num,int[] tree, int node, int start, int end, int index, int value){
        if (start == end){
            num[index] = value;
            tree[node] = value;
        }else {
            int mid = (start + end) / 2;
            int left_tree = node * 2 + 1;
            int right_tree = node * 2 + 2;
            // 判斷index在左右哪個區間里
            if (index >= start && index <= mid) {
                updateTree(num, tree, left_tree, start, mid, index, value);
            } else {
                updateTree(num, tree, right_tree, mid + 1, end, index, value);
            }
            // 修改沿途的父節點
            tree[node] = tree[left_tree]+tree[right_tree];
        }
    }

💕查找線段樹

    /**
     * 查詢線段樹
     * @param nums
     * @param tree
     * @param node
     * @param start 開始的位置仍然為0
     * @param end   結束的位置仍然為nums的長度-1
     * @param L     nums[left]
     * @param R     nums[right]
     * @return
     */
    private int queryTree(int[] nums,int[] tree, int node, int start, int end, int L, int R){
        // 不在start 和 end的范圍內
        if (R < start || L > end){
            return 0;
            // L 和 R包裹了start和end 所以直接回傳該節點值即可
        }else if (L <= start && R >= end){
            return tree[node];
            // 單個節點的情況
        }else if (start == end){
            return tree[node];
        }else{
            int mid = (start + end) / 2;
            int left_tree = 2 * node + 1;
            int right_tree = 2 * node + 2;
            int sum_left = queryTree(nums, tree, left_tree, start, mid, L, R);
            int sum_right = queryTree(nums, tree, right_tree, mid+1, end, L, R);
            // 計算和
            return sum_left+sum_right;
        }
    }