1

给定一个序列 A，其中包含 -10000 到 10000 之间的 N (N <= 50000) 个整数。在此序列上，您必须应用 M (M <= 50000) 操作：修改序列中的第 i 个元素或给定 xy打印最大值{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }。

问题链接



我为此使用段树，但没有得到正确的输出，请帮助我在哪里犯了错误
代码：

制作树：

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 的大小需要多少存储容量

4

2 回答 2

1

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

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

}

于 2015-01-09T22:30:26.170 回答
0

imo太复杂了...

int tree[1 << 17]; // 2 ^ 17 >= N * 2
int M = 1; //base of tree or sth i dont remember english name

int query(int L, int R){
  int res = -10000; //minimum possible value in array
  L += M - 1;
  R += M - 1;
  while(L <= R){
    if(L % 2 == 1) res = max(res, tree[L++];
    if(R % 2 == 0) res = max(res, tree[R++];
    L /= 2;
    R /= 2;
  }
  return res;
}

void update(int v, int value){
  v += M - 1;
  tree[v] = value;
  while(v > 0){
    v /= 2;
    tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
  }
}

void make_tree(){
  int n;
  cin >> n;
  while(M < n) M *= 2; // M is half of the size of tree
  for(int i = 0;i < n;i++)
    cin >> tree[i + M]; // just reading input to tree;
  for(int i = M - 1;i > 0;i--) // first update for all nodes other than leafs
    tree[i] = max(tree[i * 2], tree[i * 2 + 1]); 
}
于 2020-11-05T18:13:29.520 回答