Segment Tree 基础 （构造 查询 修改）

线段树的构造

Segment Tree Build

public class Build {
/**
 *@param start, end: Denote an segment / interval  
 *@return: The root of Segment Tree 
 */ 
public SegmentTreeNode build(int start, int end) { 
    // write your code here 
    if (start > end) { 
        return null; 
    } 
    SegmentTreeNode root = new SegmentTreeNode(start, end); 
    if (start == end) { 
        return root; 
    } 
    int mid = start + (end - start) / 2; 
    root.left = build(start, mid); 
    root.right = build(mid + 1, end); 
    return root; 
    }
}

Segment Tree Build II

• 对于给定无序数组，Segment Tree 可以利用递归在 O(n) 时间建立。

• Segment Tree 总共节点个数为 2n - 1，建立每个节点操作时间为 O(1).

• 另一个角度看的话，总共有 n 个叶节点，那么对应的 perfect binary tree 总节点个数就是 2n - 1.

• 结构和 quick sort \/ merge sort 非常类似，每一层包含的所有区间覆盖整个数组。

我自己的解法是每次建一个node都找一个max，可能不是递归的最好方式。

public SegmentTreeNode2 build(int[] a) { 
    // write your code here 
    int start = 0; 
    int end = a.length - 1; 
    return helper(start, end, a); 
} 
private SegmentTreeNode2 helper(int start, int end, int[] a) { 
    if (start > end) { 
        return null; 
    } 
    int max = Integer.MIN_VALUE; 
    for (int i = start; i <= end; ++i) { 
        max = Math.max(max, a[i]); 
    } 
    SegmentTreeNode2 root = new SegmentTreeNode2(start, end, max); 
    if (start == end) { 
        return root; 
    } 
    int mid = start + (end - start) / 2; 
    root.left = helper(start, mid, a); 
    root.right = helper(mid + 1, end, a); 
    return root; 
}

看了一下@mnmunknown 的解法，可能更符合divide&conquer的思想。

public class Solution {
    /**
     *@param A: a list of integer
     *@return: The root of Segment Tree
     */
    public SegmentTreeNode build(int[] A) {
        // write your code here
        return buildHelper(A, 0, A.length - 1);
    }

    private SegmentTreeNode buildHelper(int[] A, int start, int end){
        if(start > end) return null;
        if(start == end) return new SegmentTreeNode(start, end, A[start]);

        int mid = start + (end - start) / 2;

        SegmentTreeNode left = buildHelper(A, start, mid);
        SegmentTreeNode right = buildHelper(A, mid + 1, end);

        SegmentTreeNode root = new SegmentTreeNode(start, end, Math.max(left.max, right.max));
        root.left = left;
        root.right = right;

        return root;
    }
}

Segment Tree Query

@mnmunknown 的解法，非常的巧妙，判断query的查询起止位置和区间的岂止位置之间的关系。

完全体现出了递归的思想，一个大问题和分解成小问题，用一种思路去递归解决。

对于每一层的查询，最多只会分裂成两个节点：

• 如果目标区间完全不在 root 的区间里，直接返回。

  • 比如查询起始点大于所在区间结束点
  • 或者查询结束点小于所在区间起始点

  需要注意的是，我们找的是最大值，所以返回整型最小值。

• 否则设有效查询区间为

  • max(root.start, query.start)
  • min(root.end, query.end)

这段代码位置不能改变，是一种优美的解法。

public class Query1 {
 public int query(SegmentTreeNode2 root, int start, int end) {
     // write your code here
     if (start > root.end || end < root.start) {
         return Integer.MIN_VALUE; //查询的区间完全不在root的区间内，返回最小
     }

     //重新计算起止点    
     start = Math.max(start, root.start); 
     end = Math.min(end, root.end);

     //这里已经将查询区间等于root区间的情况包含了，所以后面只需要比较左右子区间即可
     //这里的判断，是整个递归精髓的一步，子问题和原问题的解决方法完美的结合起来
     if (start == root.start && end == root.end) {
         return root.max;
     }

     int left = query(root.left, start, end);
     int right = query(root.right, start, end);

     return Math.max(left, right);
     }
}

Segment Tree Query II

没什么变化，和前一道题完全一样，就是这回不求最大值，求个数，代码不贴了。