SegmentTree

class SegmentTree<T> {

    interface Operation<T> {
        T operation(T x, T y);

        T Null();
    }

    Operation<T> operation;
    T[] a;
    int size;

    SegmentTree(T[] array, Operation<T> operation) {
        this.operation = operation;
        size = 1;
        while (size < array.length) size *= 2;
        a = (T[]) new Object[2 * size - 1];
        for (int i = 0; i < array.length; i++) a[size + i - 1] = array[i];
        for (int i = array.length; i < size; i++) a[size + i - 1] = operation.Null();
        for (int i = size - 2; i >= 0; i--) a[i] = operation.operation(a[2 * i + 1], a[2 * i + 2]);
    }

    void remove(int index) {
        a[index] = operation.Null();
        while (index > 0) {
            index = (index - 1) / 2;
            a[index] = operation.operation(a[index * 2 + 1], a[index * 2 + 2]);
        }
    }

    void set(int index, T value) {
        index += size - 1;
        a[index] = value;
        while (index > 0) {
            index = (index - 1) / 2;
            int i2 = index * 2;
            a[index] = operation.operation(a[i2 + 1], a[i2 + 2]);
        }
    }

    T get(int left, int right) {
        return get(left - 1, right - 1, 0, size - 1, 0);
    }

    T get(int left, int right, int l, int r, int root) {
        if (left > r || right < l) {
            return operation.Null();
        }
        if (left <= l && right >= r) {
            return a[root];
        }
        int mid = (l + r) / 2;
        root *= 2;
        return operation.operation(get(left, right, l, mid, root + 1), get(left, right, mid + 1, r, root + 2));
    }
}