package coding4fun;

/**
 * Given an array, find an algorithm to find the minimum element of a given range.
 * The minimum element of different ranges will be called multiple times over the same array.
 *
 * <pre>
 * Input  : [3, 1, 4, 6, 2, 7]
 * Outputs: minRange(1, 4) --> 1
 *          minRange(1, 1) --> 1
 *          minRange(0, 5) --> 1
 *          minRange(0, 0) --> 3
 *          minRange(3, 5) --> 2
 * </pre>
 */
public class Problem29 {
    public static class SegmentTree {
        private final int arrayLength;

        public SegmentTree(int[] array) {
            arrayLength = array.length;
        }

        private static void build() {
            // TODO:
        }

        public int minRange(int start, int end) {
            // TODO:
            return 0;
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 1, 4, 6, 2, 7};
        SegmentTree tree = new SegmentTree(array);
        System.out.println(tree.minRange(1, 4)); // 1
        System.out.println(tree.minRange(1, 1)); // 1
        System.out.println(tree.minRange(0, 5)); // 1
        System.out.println(tree.minRange(0, 0)); // 3
        System.out.println(tree.minRange(3, 5)); // 2
    }
}

@@ -480,16 +480,50 @@
 tTree %7B%0A
+        private final int%5B%5D tree;%0A
         
@@ -636,16 +636,244 @@
 length;%0A
+            int x = (int) (Math.ceil(Math.log(array.length) / Math.log(2)));%0A            int maxSize = 2 * (int) (Math.pow(2, x)) - 1;%0A            tree = new int%5BmaxSize%5D;%0A            build(array, tree, 0, array.length - 1, 0);%0A
         
@@ -902,146 +902,1397 @@
 tic 
-void
+int
  build(
-) %7B%0A            // TODO:%0A        %7D%0A%0A        public int minRange(int start, int end) %7B%0A            // TODO:%0A            return 0
+int%5B%5D array, int%5B%5D tree, int start, int end, int current) %7B%0A            if (start == end) %7B%0A                tree%5Bcurrent%5D = array%5Bstart%5D;%0A                return tree%5Bcurrent%5D;%0A            %7D%0A            int mid = (start + end) / 2;%0A            int left = (current * 2) + 1;%0A            int right = (current * 2) + 2;%0A            int minLeft = build(array, tree, start, mid, left);%0A            int minRight = build(array, tree, mid + 1, end, right);%0A            tree%5Bcurrent%5D = Math.min(minLeft, minRight);%0A            return tree%5Bcurrent%5D;%0A        %7D%0A%0A        public int minRange(int start, int end) %7B%0A            return minRange(start, end, tree, 0, arrayLength - 1, 0);%0A        %7D%0A%0A        private int minRange(int queryStart, int queryEnd, int%5B%5D tree, int start,%0A                             int end, int current) %7B%0A            if (queryStart %3C= start && queryEnd %3E= end) %7B%0A                return tree%5Bcurrent%5D;%0A            %7D%0A            if (queryEnd %3C start %7C%7C  end %3C queryStart) %7B%0A                return Integer.MAX_VALUE;%0A            %7D%0A            int mid = (start + end) / 2;%0A            int left = (current * 2) + 1;%0A            int right = (current * 2) + 2;%0A            int minLeft = minRange(queryStart, queryEnd, tree, start, mid, left);%0A            int minRight = minRange(queryStart, queryEnd, tree, mid + 1, end, right);%0A            return Math.min(minLeft, minRight)
 ;%0A  

Add problem 29