学步园

题意：和上一篇中的意思一样，只是多了一种操作：单点更新 ，查找到叶子位置，改变一下就行~~~

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19937

代码如下

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define maxn  50010
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

struct SegNode{
    int lsum,rsum,sum,ans;
};

SegNode tree[maxn<<2];

void PushUp(int rt){
    tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
    tree[rt].lsum = max(tree[rt<<1].lsum , tree[rt<<1].sum + tree[rt<<1|1].lsum);
    tree[rt].rsum = max(tree[rt<<1|1].rsum , tree[rt<<1|1].sum + tree[rt<<1].rsum);
    tree[rt].ans = max(max(tree[rt<<1].ans , tree[rt<<1|1].ans),tree[rt<<1].rsum + tree[rt<<1|1].lsum);
}


void build(int l,int r,int rt){
    if(l == r){
        scanf("%d",&tree[rt].sum);
        tree[rt].lsum = tree[rt].rsum = tree[rt].ans = tree[rt].sum;
        return ;
    }
    int m = (l + r)/2;
    build(lson);
    build(rson);
    PushUp(rt);
}


void update(int pos,int val,int l,int r,int rt){
    if(l == r){
        tree[rt].lsum = tree[rt].rsum = tree[rt].ans = tree[rt].sum = val;
        return ;
    }
    int m = (l + r)/2;
    if(pos <= m) update(pos , val , lson);
    else update(pos , val , rson);
    PushUp(rt);
}

SegNode query(int L,int R,int l,int r,int rt){
    if(L <= l && r <= R){
        return tree[rt];
    }
    int m = (l + r)/2;
    if(R <= m) return query(L , R , lson);
    else if(L > m) return query(L , R , rson);
    else{
        SegNode result,left,right;
        left = query(L , m ,lson);
        right = query(m + 1, R, rson);
        result.sum = left.sum + right.sum;
        result.lsum = max(left.lsum , left.sum + right.lsum);
        result.rsum = max(right.rsum , right.sum + left.rsum);
        result.ans = max(max(left.ans , right.ans), left.rsum + right.lsum);
        return result;
    }
}

int n,m,op,a,b;
int main()
{
    while(~scanf("%d",&n)){
        build(1 , n , 1);
        scanf("%d",&m);
        while(m --){
            scanf("%d %d %d",&op,&a,&b);
            if(op == 1)
                printf("%d\n",query(a , b, 1 , n , 1).ans);
            else
                update(a, b, 1, n, 1);
        }
    }
    return 0;
}