Skip to content

Segment Tree Note

Jump to bottom
Xin Wan edited this page Mar 25, 2018 · 5 revisions

线段树是什么？

线段树是一种高级数据结构，也是一种树结构，准确的说是二叉树。它能够高效的处理区间修改查询等问题。

基本操作

经典问题：

操作一:给序列的第i个数加上X (X可以为负数)

操作二:询问序列中最大的数是什么? 格式query(start, end)，表示区间[start, end]内，最大值是多少？

Example:

How to build a segment tree with maxVal in the interval

/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end, max;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end, int max) {
 *         this.start = start;
 *         this.end = end;
 *         this.max = max
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param A: a list of integer
     * @return: The root of Segment Tree
     */
    public SegmentTreeNode build(int[] A) {
        if (A == null || A.length == 0) {
            return null;
        }
        
        return helper(A, 0, A.length - 1);
    }
    
    private SegmentTreeNode helper(int[] A, int left, int right) {
        if (left > right) {
            return null;
        }
        
        if (left == right) {
            SegmentTreeNode cur = new SegmentTreeNode(left, right, A[left]);
            return cur;
        }
        
        SegmentTreeNode leftNode = helper(A, left, (right + left) / 2);
        SegmentTreeNode rightNode = helper(A, (left + right) / 2 + 1, right);
        
        int maxVal = Integer.MIN_VALUE;
        if (leftNode != null) {
            maxVal = Math.max(maxVal, leftNode.max);
        }
        
        if (rightNode != null) {
            maxVal = Math.max(maxVal, rightNode.max);
        }
        
        SegmentTreeNode cur = new SegmentTreeNode(left, right, maxVal);
        cur.left = leftNode;
        cur.right = rightNode;
        
        return cur;
    }
}

构造线段树的时间复杂度和空间复杂度都为O(n)

举一反三：

*如果需要区间的最小值:

root.min = Math.min(root.left.min, root.right.min);

*如果需要区间的和:

root.sum = root.left.sum + root.right.sum;

How to modify a value (http://www.lintcode.com/en/problem/segment-tree-modify/)

public class Solution {
    /**
     * @param root: The root of segment tree.
     * @param index: index.
     * @param value: value
     * @return: nothing
     */
    public void modify(SegmentTreeNode root, int index, int value) {
        if (root == null) {
            return;
        }
        
        if (root.start == index && root.end == index) {
            root.max = value;
            return;
        }
        
        int mid = (root.end + root.start) / 2;
        if (index <= mid) {
            modify(root.left, index, value);
        } else {
            modify(root.right, index, value);
        }
        
        root.max = Integer.MIN_VALUE;
        if (root.left != null) {
            root.max = Math.max(root.max, root.left.max);
        }
        if (root.right != null) {
            root.max = Math.max(root.max, root.right.max);
        }
    }
}

复杂度 log(n)

How to query a segment?

http://www.lintcode.com/en/problem/segment-tree-query/

public class Solution {
    /**
     *@param root, start, end: The root of segment tree and 
     *                         an segment / interval
     *@return: The maximum number in the interval [start, end]
     */
    public int query(SegmentTreeNode root, int start, int end) {
        if (root == null) {
            return -1;
        }
        
        if (root.start == start && root.end == end) {
            return root.max;
        }
        
        int mid = (root.start + root.end) / 2;
        
        
        if (start > mid) {
            return query(root.right, start, end);
        } else if (end <= mid) {
            return query(root.left, start, end);
        } else {
            return Math.max(query(root.left, start, mid), query(root.right, mid + 1, end));
        }
    }
}

查询的时间复杂度为O(log(n))

什么情况下，无法使用线段树?

如果我们删除或者增加区间中的元素，那么区间的大小将发生变化，此时是无法使用线段树解决这种问题的。

Clone this wiki locally