세그먼트 트리를 사용하여 해결

Question

-10000에서 10000 사이의 정수 N (N < = 50000)의 시퀀스 A가 제공됩니다.이 시퀀스에서 M (M < = 50000) 연산을 적용해야합니다. i- 시퀀스의 x 번째 요소 또는 지정된 xy 인쇄용 max {Ai + Ai + 1 + .. + Aj | x < = i < = j < = y}.

트리 만들기 :

Problem Link

나는이에 대한 세그먼트 트리를 사용하고 있지만 내가 올바른 출력을 받고 있지 않다, 내가 실수
코드를 저지른 제발 도와주세요 :

public static void maketree(int current , int a , int b ,int[] arr){ 

     if(b<a) return; 

     if(b==a) {dp[current] = arr[a]; return ;} 

     maketree(2*current, a, (a+b)/2, arr); 

     maketree(2*current+1,1+ (a+b)/2, b, arr); 

     if(dp[2*current]>0 && dp[2*current+1]>0) dp[current] = dp[2*current] + dp[2*current+1]; 
     else if(dp[2*current]>dp[2*current+1]) dp[current] = dp[2*current]; 
     else dp[current] = dp[2*current+1]; 


} 

업데이트 기능

public static void update(int current , int a , int b , int c , int value){ 

     if(a>b || c<a || c>b) return ; 

     if(a==b){ dp[current] = value; return ; } 

     update(2*current, a, (a+b)/2, c, value); 

     update(2*current+1, (b+a)/2 +1, b, c, value); 

     if(dp[2*current]>0 && dp[2*current+1]>0) dp[current] = dp[2*current] + dp[2*current+1]; 
     else if(dp[2*current]>dp[2*current+1]) dp[current] = dp[2*current]; 
     else dp[current] = dp[2*current+1]; 



} 

쿼리 기능 :

public static int query(int current , int a , int b , int i , int j){ 
     int ans =0; 


     if(a>j || b<i || a>b) return Integer.MIN_VALUE; 

     if(a>=i && b<=j) return dp[current]; 

     int x = query(2*current, a, (a+b)/2, i, j); 
     int y = query(2*current+1, (a+b)/2 +1, b, i, j); 

     if(x>0 && y>0) ans= x+y; 
     else if(x>y) ans = x; 
     else ans =y; 





     return ans; 



} 

나는 돈, t는 저장 용량이 dp array 즉, DP의 크기

Answer 1

에 필요한 것 무엇, 내가 실수 도와주세요 만든 위치를 알

두 노드를 병합 할 때 아래에 주어진 것과 같을 수 있습니다. 간단한 예제를 통해 느낄 수 있습니다.

무효 병합 (노드 A, 노드 B)
{

sum = a.sum + b.sum; 
    pre = max(a.pre , (a.sum + b.pre)); 
    suf = max(b.suf , (b.sum + a.suf)); 
    result = max(a.suf + b.pre,max(a.result , b.result)); 

}