algorithm - 段树正确，但查询输出不正确

我尝试在java中实现段树算法来查找范围最小查询。这是我完整的java代码它从数组中构建段树然后打印每个范围内的最小元素问题是，tree是正确的（据我所知），但输出始终是整个数组中最小的元素。●请指出我错在哪里。

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();
 }
}

最佳答案

您必须在代码中进行以下更改。
首先，用于在分段树数据结构中存储数据的数组大小应该是给定数组大小的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;
}

希望这有帮助。

关于algorithm - 段树正确，但查询输出不正确，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53466563/