c++ - SPOJ GSS1 WA - 线段树

Question

我正在尝试解决 SPOJ 问题 GSS1 (你能回答我的这些问题吗)使用 segment tree .我正在使用“init”方法初始化一棵树，并使用“query”方法在 [i,j] 范围内获得最大值。

极限 |A[i]| <= 15707 和 1<=N(元素数)<=50000。

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)，但我无法弄清楚算法出了什么问题。

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

谢谢

Answer 1

我担心(已接受的)答案错过了这里非常重要的一点。问题在于代码本身使用的算法。代码表示节点的答案是其子节点值的最大值。但很有可能最大子数组部分位于两个子数组中。例如

-1 -2 3 4 5 6 -5 -10 (n=8)

当答案为 18 时，代码将输出 11。

您还需要调查此案例才能打败 WA。 (我正在回答这个问题，因为接受的答案并不完全正确，也没有正确回答这个问题。)