1

我有一个关于区间树的问题要解决，并且我基本上知道算法，但是当我的函数将值返回给它的主要值时，我的代码中有问题。

我遇到的问题是找到某些索引之间的最大值，并更新数组中的某些值。所以有一个具有 n 个数字和 m 个操作的初始数组。如果操作从 0 开始，我应该对 index 之间的最大值进行询问x。x如果操作从 1 开始，我应该用 更新初始向量上的索引值y。

问题是，在某些询问中，它会在文件中检索正确答案，而在某些情况下，它只是给出一些“随机”数字。

我在代码期间做了一些 printf 以便我可以监视答案，我看到最后，在函数中，在返回值之前它是完全正确的，当我在函数之后立即在 main 中检查它时，它给了我结果我告诉你了。

这是我正在测试的输入：

5 5
4 3 5 6 1
0 1 3
1 3 2
0 2 3
1 4 2
0 1 5

代码：

#include <stdio.h>
FILE *fin, *fout;
int pos, val, m, n, *arb;
bool f;
int max(int a, int b);
void pun(int nod, int st1, int dr1);
int interogare(int nod, int st1, int dr1, int st2, int dr2);
int main()
{
    fin = fopen("arbori.in", "r");
    fout = fopen("arbori.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    arb = new int[2*n];
    for(int i = 1; i<= 2*n - 1; i++) arb[i] = 0;
    for(int i =1; i<= n; i++)
    {
            pos = i;
            fscanf(fin, "%d", &val);
            pun(1, 1, n);
    }
    for(int i =1; i<= m; i++)
    {
            fscanf(fin, "%d", &f);
            if(f == 1)
            {
                 fscanf(fin, "%d%d", &pos, &val);
                 pun(1, 1, n);
            }
            else
            {
                fscanf(fin, "%d%d", &pos, &val);
                fprintf(fout, "%d\n", interogare(1, 1, n, pos, val));//if i check it here it's not good
            }
    }
    return 0;
}
int max(int a, int b)
{
    return (a> b)?a:b;
}
void pun(int nod, int st1, int dr1)//update function - working properly
{
     if(st1 == dr1)
     {
            arb[nod] = val;
            return ;
     }
     int mij = (st1 + dr1)/2;
     if(pos <= mij) pun(2*nod, st1, mij);
     else pun(2*nod+1, mij +1, dr1);
     arb[nod] = max(arb[2*nod + 1], arb[2*nod]);
     return ;
}
int interogare(int nod, int st1, int dr1, int st2, int dr2)//interogation function
{
    if(st1 == st2 && dr1 == dr2) return arb[nod];//if i check my result here it is the expected one
    int mij = (st1 + dr1)/2;
    if(st2 > mij) interogare(2*nod+1, mij+1, dr1, st2, dr2);
    if(dr2 <= mij) interogare(2*nod, st1, mij, st2, dr2);
    if(st2 <= mij && dr2 > mij) return max(interogare(2*nod, st1, mij, st2, mij),interogare(2*nod+1, mij + 1, dr1, mij + 1, dr2));
}

对不起，很长的帖子和很长的代码，如果我遗漏了什么，请提醒我。

先感谢您！

4

1 回答 1

1

当您interogare递归调用时，您不会返回结果：

int interogare(int nod, int st1, int dr1, int st2, int dr2)//interogation function
{
    if(st1 == st2 && dr1 == dr2) return arb[nod];//if i check my result here it is the expected one
    int mij = (st1 + dr1)/2;
    if(st2 > mij) return interogare(2*nod+1, mij+1, dr1, st2, dr2);
    if(dr2 <= mij) return interogare(2*nod, st1, mij, st2, dr2);
    if(st2 <= mij && dr2 > mij) return max(interogare(2*nod, st1, mij, st2, mij),interogare(2*nod+1, mij + 1, dr1, mij + 1, dr2));
}
于 2014-11-02T09:33:57.897 回答