c++ - 间隔树 - 主要功能障碍的功能

Question

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

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

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

我在代码中做了一些 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));
}

抱歉，帖子和代码很长，如果我遗漏了什么，请提醒我。

提前致谢!

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