摘要：// 判斷是否需要去左子樹查找 if (start mid) { leftMax = query(root.left, start, mid)。} } // 判斷是否需要去右子樹查找 if (mid < end) { // 節點相交查找區間的情況 if (start <= mid) { rightMax = query(root.right, mid + 1, end)。

        <div>
點擊關注上方“ 五分鐘學算法 ”，

設爲“置頂或星標”，第一時間送達乾貨。

來源：五分鐘學算法

一、概念解析

這次來介紹一個數據結構 - 線段樹。

在平時刷題或是工作中，經常會遇到這麼一個問題，“ 給定一個數組，求出數組某段區間的一些性質 ”。

比如給定一個數組 [5,2,6,1,-4,0,9,2] ，讓你求出區間 [1,4] 上所有元素的和，在這個例子中，答案是 2 + 6 + 1 + (-4) = 5 。

你可能會說，直接遍歷一遍不就好了嗎？

最簡單的方式就是直接遍歷一遍區間，時間複雜度也顯而易見 O(n) ，如果在這個數組上頻繁進行這個操作，那麼效率相對來說會比較低，怎麼優化呢？

對於求區間和的問題， 前綴和數組 是一個不錯的選擇，構建好前綴和數組後，求一個區間和的話只要前後一減就可以了，如果不算構建數組的時間，那麼每次的操作時間複雜度就是 O(1) 。

這裏的問題在於 前綴和數組只能解決求區間和的問題，但是其他的區間問題，前綴和數組並不能很好的解決，比如求某段區間上的最大值 。

因此我們需要一個數據結構能夠幫助我們解決大部分數組的區間問題，而且時間複雜度要儘可能的低。

這也就是今天的主題 - 線段樹，首先要說明一點的是，線段樹也是二叉樹，只是它的節點裏面含有區間的信息。

線段樹每個節點表示的是一個區間，每個節點將其表示的區間一分爲二，左邊分到左子樹，右邊分到右子樹，根節點表示的是整個區間（也就是整個數組），葉子節點表示的是一個 index（也就是單個元素），因爲每次對半分的緣故，線段樹構建出來是平衡的，也就是說樹的高度是 O(logn) ，這裏的 n 表示的是數組中所有的元素，這一點對於我們後面分析複雜度很重要。

線段樹有三個基本的操作，分別是 構建線段樹(build) 、 區間查找(query) 、還有就是 修改(modify) ，假設我們現在需要解決的問題是 “ 求區間上的最大值 ”，例子還是之前的例子，一起來看看怎麼實現這些操作。

對於構建操作來說，相對簡單，你只需要記住 “ 自上而下而下遞歸分裂，自下而上回溯更新 ” 從根節點到葉子節點我們不斷地將區間一分爲二，從葉子節點開始返回值，一直到根節點，不斷地更新區間信息。

查找操作是線段樹的核心操作，考慮的情況相對較多，這裏有四種情況：

  • 情況一：節點區間 包含 查找區間。這種情況直接遞歸向下查找即可

  • 情況二：節點區間 不相交 於查找區間。因爲沒有要查找的範圍，停止搜索

  • 情況三：節點區間 相交但不包含 查找區間。將區間分成兩段，分別查找

  • 情況四：節點區間 相等於 查找區間。直接返回答案

說明一下，這裏說的 “包含” 的意思是一個區間全部元素都被另外一個區間涵蓋，“相交” 的意思是一個區間的部分元素被另外一個區間涵蓋，例如要查找的區間是 [1,3] ，那麼 [0,4] 包含要查找的區間， [2,5] 只是相交要查找的區間。對於區間查找，後面有圖解，跟着例子走一遍印象會更深刻。

最後一個修改操作，和構建操作類似，但有些許不同，你只需要記住 “ 自上而下遞歸查找，自下而上回溯更新 ”。修改的意思是，修改數組中的一個元素的值，這會影響相關的區間，相關的樹節點，因此，相關聯的節點也就需要更新。

線段樹靈活的地方在於，樹節點中存放的數據不同，它的功能就不同，比如說，你想要求解區間和，那麼樹節點中就存放對應區間元素的和，你想求解區間上的最大值，那麼樹節點中存放的就是對應區間上的最大值。不過話說回來，線段樹並不是一個被廣泛應用的數據結構，原因可能在於線段樹的構建和使用相對於前綴和數組這樣的技巧來說，稍微複雜了些。但是在解決數組區間的問題上，線段樹可以提供一個還不錯的思考方向。

二、動畫描述

三、代碼實現 

public class Solution {
    private class SegmentTreeNode {
        int start, end, max;
        SegmentTreeNode left, right;
        SegmentTreeNode(int start, int end, int max) {
            this.start = start;
            this.end = end;
            this.max = max;
            this.left = this.right = null;
        }
    }

    public SegmentTreeNode build(int start, int end, int[] nums) {
        if (start > end) {
            return null;
        }

         if (start == end) {
            return new SegmentTreeNode(start, end, nums[start]);
         }

        SegmentTreeNode node = new SegmentTreeNode(start, end, nums[start]);

        // 自上而下而下遞歸分裂
        if (start != end) {
            int mid = (start + end) / 2;
            node.left = build(start, mid, nums);
            node.right = build(mid + 1, end, nums);
        }

        // 自下而上回溯更新
        if (node.left != null && node.left.max > node.max) {
            node.max = node.left.max;        
        }

        if (node.right != null && node.right.max > node.max) {
            node.max = node.right.max;        
        }

        return node.max;
    }

    public int query(SegmentTreeNode root, int start, int end) {
         // 如果節點區間相等於查找區間，直接返回對應的值即可
        if (root.start == start && root.end == end) {
            return root.max;
        }

        int mid = (root.start + root.end) / 2;
        int leftMax = Integer.MIN_VALUE, rightMax = Integer.MIN_VALUE;

        // 判斷是否需要去左子樹查找
        if (start <= mid) {
            // 節點相交查找區間的情況
            if (end > mid) {
                leftMax = query(root.left, start, mid);
            } // 節點包含查找區間的情況
            else {
                leftMax = query(root.left, start, end);
            }
        }

        // 判斷是否需要去右子樹查找
        if (mid < end) {
            // 節點相交查找區間的情況
            if (start <= mid) {
                rightMax = query(root.right, mid + 1, end);
            } // 節點包含查找區間的情況
            else {
                rightMax = query(root.right, start, end);
            }
        }

        return Math.max(leftMax, rightMax);
    }

    public void modify(SegmentTreeNode root, int index, int value) {
        // 找到對應的葉子節點，進行元素更新
        if (index == root.start && index == root.end) {
            root.max = value;
        }

        if (root.start >= root.end) {
            return;
        }

         // 自上而下遞歸查找         
        modify(root.left, index, value);
        modify(root.right, index, value);

        // 自下而上回溯更新
        root.max = Math.max(root.left.max, root.right.max);
    }
}

四、複雜度分析

三個操作中，構建樹的操作的時間複雜度是 O(n) ，原因也很好解釋，構建的樹有 2n 個節點，你可能會問這個 2n 是怎麼得到的，思考這個問題可以從葉子節點出發，一共有 n 個葉子節點，構建操作是從上往下不斷二分，這樣保證了樹的平衡，因此所有節點個數就是 n + n/2 + n/4 + ... + 1 = 2n 。

由於構建每個節點只花了 O(1) 的時間，因此整個構建的時間複雜度就是 O(2n) ，忽略常數項，也就是 O(n) 。

修改和查找都是沿着一條或者幾條從上到下的路徑進行的，因爲樹的高度是 O(logn) ，所以這兩個操作的時間複雜度也是 O(logn) 。可以看到這個時間複雜度比暴力的 O(n) 還是快不少。

END

相關文章