間隔樹 - 主要功能障礙

Question

我有一個問題的區間樹來解決，我知道基本的算法，但我的代碼時，我的函數返回一個值，它是主要的問題。

我遇到的問題是找到特定索引之間的最大值，並更新數組中的某個值。所以有一個包含n個數字和m個操作的初始數組。如果操作從0開始，我應該在索引x之間的最大值處進行interogation。如果操作從1開始，我應該用y更新初始向量索引x上的值。

問題是，在一些interogations它在文件中檢索正確的答案，並在一些它只是給一些「隨機」數字。

我在代碼中做了一些printf，以便我可以監視答案，並且在函數結束時看到，在返回值之前它是完全正確的，當我在函數後面檢查它時，給了我我告訴過你的結果。

這是我測試的輸入：

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