Дерево сегментов правильное, но вывод запроса не

Question

Я попытался реализовать алгоритм дерева сегментов для поиска минимального диапазона поиска в Java. Вот мой полный java код. Он строит дерево сегментов из массива. а затем печатает минимальный элемент в каждом диапазоне. проблема в том, что дерево корректно (насколько я знаю), но вывод всегда является наименьшим элементом всего массива.:-| пожалуйста, укажите, где я иду не так.

public class Solution {

static int arr[] = {-1, 2, 4, 0};
static int st[];

public static void main(String[] args) {

    st = new int [ 2 * arr.length-1];

    buildTree(0, 0, arr.length-1);

    System.out.print("original array: ");
    showArray(arr);

    System.out.print("segment tree: ");
    // shows segment tree
    showArray(st);

    System.out.println("\nqueries: \n");

    // prints minimum in every range
    for(int i=0; i<arr.length; i++) {
        for(int j=i+1; j<arr.length; j++) 
            System.out.println(i+":"+j+" -> "+search(i, j));
    }

}

// builds segment tree
static void buildTree(int pos, int left, int right) {

    if(left == right) {
        st[pos] = arr[left];
        return;
    }

    int mid = (left + right) / 2;

    buildTree(left(pos), left, mid);
    buildTree(right(pos), mid+1, right);

    int p1 = left(pos);
    int p2 = right(pos);

    st[pos] = (st[p1] > st[p2]) ? st[p2] : st[p1];
}

// left child
static int left(int pos) {
    return pos * 2 + 1;
}

// right child
static int right(int pos) {
    return pos * 2  + 2;
}

static int search(int left, int right) {

     return rmq(0, 0, st.length, left, right);
}

// range minimum query function
static int rmq(int pos, int left, int right, int qleft, int qright) {

    if((qleft > right) && (qright < left))
        return Integer.MAX_VALUE;

    if((qleft <= left) || (qright >= right))
        return st[pos];

    int mid = (left + right) / 2;

    int l = rmq(left(pos), left, mid, qleft, qright);
    int r = rmq(right(pos), mid + 1, right, qleft, qright);

    return (l > r) ? r : l;
}

// show segment tree
static void showArray(int arr[]) {

    for(Integer x : arr)
        System.out.print(x+" ");
    System.out.println();
 }
}

Answer 1

Вы должны внести следующие изменения в свой код.

Прежде всего размер массива, используемого для хранения данных в сегментарной структуре данных, должен быть в 4 раза больше размера данного массива. Вот почему?

st = new int [ 4 * arr.length - 1];

Далее в search функция, третий параметр для rmq должно быть arr.length - 1,

static int search(int left, int right) {
     return rmq(0, 0, arr.length - 1, left, right);
}

И, наконец, вы должны исправить базовые случаи и аргументы в дочерних вызовах в rmq функционировать следующим образом:

static int rmq(int pos, int left, int right, int qleft, int qright) {

    if((qleft > right) || (qright < left))
        return Integer.MAX_VALUE;

    if((qleft <= left) && (qright >= right))
        return st[pos];

    int mid = (left + right) / 2;

    int l = rmq(left(pos), left, mid, qleft, Math.min(qright, mid) );
    int r = rmq(right(pos), mid + 1, right, Math.max(mid + 1, qleft), qright);

    return (l > r) ? r : l;
}

Надеюсь это поможет.