HDU 1754単点更新区間求和zkw線分ツリー+再帰線分ツリー

//lrl's submission
#include
#include
#include
using namespace std;

#define debug 0
#define ls  root << 1, l, mid
#define rs  root << 1 | 1, mid + 1, r
#define M(a, b) memset(a, b, sizeof(a))

const int maxn = 200000 + 5;
int mx[maxn << 2], n, m, ip = 0;

void pushUp(int root){
    mx[root] = max(mx[root << 1], mx[root << 1|1]);
}
void build(int root, int l, int r){
    if(l == r){
        scanf("%d", &mx[root]);
        return;
    }
    //printf("%d %d
", l, r);
    //ip++;
    //if(ip == 6)
        //return;
    //return;
    int mid = (l + r) >> 1;
    build(ls);
    build(rs);
    pushUp(root);
}
void update(int root, int l, int r, int a, int b){
    if(l == r){
        if(l == a){
            mx[root] = b;
        }
        return;
    }
    if(a < l || a > r)
        return;
    int mid = (l + r) >> 1;
    update(ls, a, b);
    update(rs, a, b);
    pushUp(root);
}
int query(int root, int l, int r, int a, int b){
    if(b < l || a > r)
        return 0;
    if(a <= l && r <= b)
        return mx[root];
    int mid = (l + r) >> 1;
    return max(query(ls, a, b), query(rs, a, b));
}
int main()
{
#if debug
    freopen("in.txt", "r", stdin);
#endif // debug
    char s[5];
    int a, b;
    while(~scanf("%d%d", &n, &m))
    {
        //printf("%d %d
", n, m);
        M(mx, 0);
        build(1, 1, n);
        while(m--)
        {
            scanf("%s%d%d", s, &a, &b);
            //printf("%d %d
", a, b);
            if(s[0] == 'Q'){
                printf("%d
", query(1, 1, n, a, b));
            }
            else{
                update(1, 1, n, a, b);
            }
        }
    }
    return 0;
}

//lrl's submission
#include
#include
#include
using namespace std;

#define debug 0
#define mid (l + r) >> 1
#define ls  root << 1, l, mid
#define rs  root << 1 | 1, mid + 1, r
#define M(a, b) memset(a, b, sizeof(a))

const int maxn = 200000 + 5;
int mx[maxn << 2], n, m, M;
void build()
{
    for(M = 1; M <= n + 1; M <<= 1);
    for(int i = M + 1; i <= M + n; i++){
        scanf("%d", &mx[i]);
    }
    for(int i = M - 1; i >= 1; i--)
        mx[i] = max(mx[i << 1], mx[i << 1|1]);
}
void update(int a, int b){
    for(mx[a += M] = b, a >>= 1; a; a >>= 1)
        mx[a] = max(mx[a << 1], mx[a << 1|1]);

}
int query(int a, int b){
    a += M - 1;
    b += M + 1;
    int ans = 0;
    while(b - a > 1){
        if(a % 2 == 0){
            ans = max(ans, mx[a + 1]);
        }
        if(b % 2)
            ans = max(ans, mx[b - 1]);
        a >>= 1;
        b >>= 1;
     }
     return ans;
}
int main()
{
#if debug
    freopen("in.txt", "r", stdin);
#endif // debug
    char s[5];
    int a, b;
    while(~scanf("%d%d", &n, &m))
    {
        //printf("%d %d
", n, m);
        M(mx, 0);
        build();
        while(m--)
        {
            scanf("%s%d%d", s, &a, &b);
            //printf("%d %d
", a, b);
            if(s[0] == 'Q'){
                printf("%d
", query(a, b));
            }
            else{
                update(a, b);
            }
        }
    }
    return 0;
}