线段树正确但查询输出不正确

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

您必须对代码进行以下更改。

首先，用于在segmentree 数据结构中存储数据的数组大小应该是给定数组大小的4 倍。 Here是为什么？

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

希望对您有所帮助。

线段树正确但查询输出不正确

segment tree correct but query output is not

algorithm

data-structures

segment-tree

rmq