Segment Tree Build

Most fundamental operation of segment tree.

Segment Tree Build

Analysis: Recursively build SegmentTreeNodes with given range. When start == end, the node will be a leaf node

public SegmentTreeNode build(int start, int end) {
        SegmentTreeNode new_node = new SegmentTreeNode(start, end);
        // Invalid range
        if (end < start)
            return null;
        // Leaf node
        if (start == end)
            return new_node;

        new_node.left = build(start, (start+end)/2);
        new_node.right = build((start+end)/2+1, end);

        return new_node;
    }

Segment Tree Build II

Analysis: In this problem, segment tree node adds a new attribute max. The input becomes an array whose values are correspond leaf node's max attribute.

From the array, we can get following information:

1. The length of array is the number of leaves of the tree
2. The range of the root is [ 0, array.length-1]

Therefore, we can build a root with range [ 0, array.length-1]. And its max value is the max_value of the array.

Then, recursively build its left and right child with divided ranges and divided arrays.

Example: Given array [3, 2, 1, 4]

1 Build the root with range [0, 3], and max = 4

2 Build root's left child with start=0, end=1, array=[3,2]

3 Build root's right child with start=2, end=1, array=[1,4]

4 Recursively build nodes till reach leaf nodes

public SegmentTreeNode build(int[] A) {
        return buildHelper(A, 0, A.length - 1);
    }
    // Utility function
    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;
    }