c++ - SPOJ GSS1 WA-段树

我正在尝试使用GSS1解决SPOJ问题segment tree（您能回答这些问题吗）。我正在使用'init'方法初始化一棵树，并使用'query'方法来获取范围[i，j]中的最大值。

极限| A [i] |

int A[50500], tree[100500];

void init(int n, int b, int e) // n=1, b=lower, e=end
{
    if(b == e)
    {
        tree[n] = A[b];
        return;
    }
    init(2 * n, b, (b + e) / 2);
    init(2 * n + 1, ((b + e) / 2) + 1, e);

    tree[n] = (tree[2 * n] > tree[2 * n + 1]) ? tree[2 * n] : tree[2 * n + 1];
}

int query(int n, int b, int e, int i, int j) // n=1, b=lower, e=end, [i,j]=range
{
    if(i>e || j<b)
        return -20000;
    if(b>=i && e<=j)
        return tree[n];

    int p1 = query(2 * n, b, (b + e) / 2, i, j);
    int p2 = query(2 * n + 1, ((b + e) / 2) + 1, e, i, j);

    return (p1 > p2) ? p1 : p2;
}

程序给出了错误的答案。在大多数情况下（例如，负数，奇数/偶数N），我都对代码进行了调试，但是我无法弄清楚算法出了什么问题。

如果有人能指出正确的方向，我将不胜感激。

谢谢

最佳答案

编辑：看来您的实现也是正确的，我只是有另一个。而且我们都误解了问题说明。



我想你用params调用你的query函数

query( 1, 0, n-1, x-1, y-1 );

我认为，当您的n不是2的pow时，以这种方式处理段树是错误的。
我为您提供


将tree数组扩展为131072个元素（2 ^ 17），将A扩展为65536（2 ^ 16）;
发现最小的k不小于n并且是2的战俘；
用-20000初始化从n（从0开始）到k-1的元素;
使n等于k;
确保您致电init(1,0,n-1);


希望对您有所帮助。

关于c++ - SPOJ GSS1 WA-段树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11898879/