解决一个用线段树 [英] Solving a using Segment Tree

问题描述

您给出N的序列A（N＆LT; = 50000）-10000和10000之间的整数。在这个序列，你必须使用M（M＆LT; = 50000）操作： 修改的第i个元素中的序列，或对于给定的xy打印最大{艾+艾+ 1 + .. + AJ | X - LT; = I＆LT; = J＆LT; = Y}

You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations: modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

问题链接

我使用的段树的这一点，但我没有得到正确的输出，请帮我在哪里，我都犯了错
code：

制作树：

I am using Segment Tree for this but i am not getting the correct output , please Help me where i have committed the mistake
CODE:

Making a Tree:

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阵列即DP的尺寸

推荐答案

当你合并两个节点，那么它可能会像给below.execute任何简单的例子，让你能感觉到：）

when you are merging two nodes,then it may be like given below.execute any simple example so that you can feel it :)

无效合并（节点，节点B）
{

void merge(node a , node 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));

}

这篇关于解决一个用线段树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！