0711 Can you answer these queries I

线段树，修改，维护区间最大最小、和；

Description

维护一个整数序列，支持以下操作：
1 x v : 将第x个整数的值修改为v；
2 x y : 查询区间[x,y]之间的最小值；
3 x y : 查询区间[x,y]之间的最大值；
4 x y : 查询区间[x,y]内的整数和。

Input

输入文件包含多组测试数据。
对于每组测试数据，第一行为一个整数N(1<=N<=10^5)，表示，接下来一行有N个整数，再接下来一行有一个整数M(1<=M<=10^5)，表示一共有M个操作。
数据保证对于查询操作结果均在int的表示范围内。

Output

对于每个查询均用一行输出查询的结果。

Sample Input

4 1 5 3 4 5 2 2 4 3 1 3 4 1 4 1 3 -3 4 1 4

Sample Output

3 5 13 7

----------------------------------------------------------------

# include <stdio.h>
# include <string.h>

# define N 100005
# define INF 0x7fffffff

int n, m, D;
int Max[4 * N], Min[4 * N], Sum[4 * N];

int max(int x, int y)
{
    return x>y ? x:y;
}

int min(int x, int y)
{
    return x<y ? x:y;
}

void update(int i)
{
    for (i += D; i ^ 1; i >>= 1)
    {
        Sum[i >> 1] = Sum[i] + Sum[i ^ 1];
        Max[i >> 1] = max(Max[i], Max[i ^ 1]);
        Min[i >> 1] = min(Min[i], Min[i ^ 1]);
    }
}

int query(int s, int t, int bj)
{
    int ret;

    if (bj == 4) ret = 0;
    else ret = (bj==2 ? INF:-INF);

    s += D-1, t += D+1;
    for (; s ^ t ^ 1; s >>= 1, t >>= 1)
    {
        if ((~s) & 0x1)
        {
            if (bj == 4) ret += Sum[s+1];
            else ret = (bj==2 ? min(ret, Min[s+1]):max(ret, Max[s+1]));
        }
        if ( t & 0x1)
        {
            if (bj == 4) ret += Sum[t-1];
            else ret = (bj==2 ? min(ret, Min[t-1]):max(ret, Max[t-1]));
        }
    }

    return ret;
}

void init(void)
{
    int i, num;
    
    for (D = 1; D < n+2; D <<= 1) ;
    for (i = 0; i <= 2*D+2; ++i)
    {
        Sum[i] = 0;
        Min[i] = INF;
        Max[i] = -INF;
    }

    for (i = 1; i <= n; ++i)
    {
        scanf("%d", &num);
        Max[i+D] = Min[i+D] = Sum[i+D] = num;
        update(i);
    }
}

void solve(void)
{
    int i, bj, p, q;

    scanf("%d", &m);
    for (i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &bj, &p, &q);
        if (bj == 1) Sum[D+p] = Min[D+p] = Max[D+p] = q, update(p);
        else printf("%d\n", query(p, q, bj));
    }
}

int main()
{
    while (~scanf("%d", &n))
    {
        init();
        solve();
    }

    return 0;
}

----------------------------------------------------------------