Segment Tree

import java.util.Arrays;

public class SegmentTree {

    private final int[] data;

    SegmentTree(final int[] values) {

        int x = 1;
        //Search for the first
        //power of 2 greater then n
        while (x < values.length) {
            x *= 2;
        }

        data = new int[2 * x - 1];
        for (int i = 0; i < data.length; i++) {
            data[i] = Integer.MAX_VALUE; //Infinity
        }
        System.arraycopy(values, 0, data, getOffset(), values.length);

        //Restore invariants
        int offset = getOffset();

        //Count of nodes to be examined
        int limit = data.length - offset - 1;
        while (limit >= 1) {
            for (int i = 0; i < limit; i += 2) {
                final int left = i + offset;
                final int right = left + 1;
                final int min = Math.min(data[left], data[right]);

                //Change parents value to the minimum of its children
                int parentIdx = (left + 1) / 2 - 1;
                data[parentIdx] = min;
            }

            limit >>>= 1; //Proceed twice as less as in current step
            offset = (offset + 1) / 2 - 1; //Move one level up the heap
        }

    }

    public int min(final int left, final int right) {

        final int rangeEnd = data.length - data.length / 2;

        return getMinOnRange(1, rangeEnd, left, right);
    }

    private int getMinOnRange(final int rangeStart, final int rangeEnd,
                              final int left, final int right)
    {
//            System.out.println("[" + rangeStart + ", " + rangeEnd + "]");
//            System.out.println("(" + left + ", " + right + ")");

        if (left == right) return getSingleValue(left);

        if (rangeStart == left && rangeEnd == right) {
            return getCachedValue(rangeStart, rangeEnd);
        }

        final int mid = (rangeStart + rangeEnd) / 2; //Mid is always even

        if (mid > left && mid < right) {

            return Math.min(getMinOnRange(rangeStart, mid, left, mid),
                    getMinOnRange(mid + 1, rangeEnd, mid + 1, right));

        } else if (mid < left) {

            return getMinOnRange(mid + 1, rangeEnd, left, right);

        } else if (mid >= right) {

            return getMinOnRange(rangeStart, mid, left, right);

        } else {

            return Math.min(getMinOnRange(rangeStart, mid, left, mid),
                    getMinOnRange(mid + 1, rangeEnd, mid + 1, right));
        }
    }

    private int getSingleValue(final int idx) {
        return data[getOffset() + idx - 1];
    }

    private int getCachedValue(final int rangeStart, final int rangeEnd) {
        int diff = rangeEnd - rangeStart + 1;
        int realIdx = getOffset() + rangeStart - 1;

        while (diff > 1) {
            //Move to the
            realIdx = (realIdx + 1) / 2 - 1;
            diff /= 2;
        }

        return data[realIdx];
    }

    public void set(final int pos, final int value) {
        final int offset = getOffset();
        final  int realIdx = offset + pos - 1;
        data[realIdx] = value;

        restoreInvariant(realIdx);
    }

    public String toString() {
        return Arrays.toString(data).replaceAll(
                String.valueOf(Integer.MAX_VALUE),
                "inf"
        );
    }

    private int getOffset() {
        //Leaves of the heap
        //start from this index
        //Heap size is 2^n - 1 thus
        //offset points exactly to the first leave
        return data.length / 2;
    }

    private void restoreInvariant(final int idx) {
        //If root then return
        if (idx == 0) {
            return;
        }

        final int left = ((idx & 1) == 0) ? idx - 1: idx;
        final int right = left + 1;
        final int parentIdx = (left + 1) / 2 - 1;

        data[parentIdx] = Math.min(data[left], data[right]);

        restoreInvariant(parentIdx);
    }
}