给你一个N(N修改序列中的第i个元素,或者对于给定的x y print max{ai+ai+1+…+aj xProblem 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;



}

我不知道我在哪里犯了错误,请帮忙,对于dp array所需的存储容量是多少,即dp的大小

最佳答案

当您合并两个节点时,可能如下所示。执行任何简单的示例,以便您能感觉到:)
无效合并(节点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));

}

关于java - 解决使用分段树,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/27866274/

10-09 15:33