hdoj 1166

 

题意：略。

思路：基础的线段树，静态建树，更新结点，查询信息。代码如下：

#include<iostream>
using namespace std;
const int Max = 50005;

struct data
{
    int l, r, num;
}node[3*Max];     //  线段树节点的数据结构。
int num[Max];

void BuildTree(int left, int right, int u)
{      //  建树。
    node[u].l = left;
    node[u].r = right;
    if(left == right) 
        node[u].num = num[left];
    else
	{
        BuildTree(left, (left+right)/2, 2*u);
        BuildTree((left+right)/2+1, right, 2*u+1);
        node[u].num = node[2*u].num + node[2*u+1].num;
    }
}

int updata(int camp, int w, int u)
{              //  修改。
    node[u].num += w;
    if(node[u].l == node[u].r) 
		return 0;
    else 
		if(camp <= node[2*u].r) 
			updata(camp, w, 2*u);
    else 
		updata(camp, w, 2*u+1);
    return 0;
}

int query(int left, int right, int u)
{           //  查询。
    if(node[u].l == left && node[u].r == right)
        return node[u].num;
    if(right <= node[2*u].r)
        return query(left, right, 2*u);
    if(left >= node[2*u+1].l)
        return query(left, right, 2*u+1);
    int a = query(left, (node[u].l+node[u].r)/2, 2*u);
    int b = query((node[u].l+node[u].r)/2+1, right, 2*u+1);
    return a + b;
}

int main()
{
    int t, k, n;
    scanf("%d", &t);
    for(k = 1; k <= t; k ++)
	{
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++)
            scanf("%d", &num[i]);
        BuildTree(1, n, 1);
        printf("Case %d:\n", k);
        char str[10];
        while(cin >> str && str[0] != 'E')
		{
            int a, b;
            scanf("%d%d", &a, &b);
            if(str[0] == 'A') 
				updata(a, b, 1);
            else if(str[0] == 'S') 
				updata(a, -b, 1);
            else 
				printf("%d\n", query(a, b, 1));
        }
    }
    return 0;
}

 

hdoj 1754与这道题目类似，也是静态建树，修改结点休息，最后查询。

代码如下：

#include<iostream>
using namespace std;
const int Max = 200050;

struct data
{
    int l, r, max;
}node[3*Max];
int score[Max];

int max(int a, int b)
{
    return a > b ? a : b;
}

void BuildTree(int left, int right, int u)
{      //  建树。
    node[u].l = left;
    node[u].r = right;
    if(left == right)
        node[u].max = score[left];
    else
	{
        BuildTree(left, (left+right)/2, 2*u);
        BuildTree((left+right)/2+1, right, 2*u+1);
        node[u].max = max(node[2*u].max, node[2*u+1].max);
    }
}

void updata(int stu, int val, int u)
{            //  修改。
    if(node[u].l == node[u].r)
	{
        node[u].max = val;
        return;
    }
    if(stu <= node[2*u].r) 
		updata(stu, val, 2*u);
    else 
		updata(stu, val, 2*u+1);
    node[u].max = max(val, node[u].max);
}

int query(int left, int right, int u)
{           //  查询。
    if(node[u].l == left && node[u].r == right)
        return node[u].max;
    if(right <= node[2*u].r)
        return query(left, right, 2*u);
    if(left >= node[2*u+1].l)
        return query(left, right, 2*u+1);
    int mid = (node[u].l + node[u].r) / 2;
    return max(query(left, mid, 2*u), query(mid+1, right, 2*u+1));
}

int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF)
	{
        for(int i = 1; i <= n; i ++)
            scanf("%d", &score[i]);
        getchar();       //  记得收回回车符。
        BuildTree(1, n, 1);
        while(m--)
		{
            int a, b;
            char order;
            scanf("%c%d%d", &order, &a, &b);
            if(order == 'U') 
				updata(a, b, 1);
            if(order == 'Q') 
				cout << query(a, b, 1) << endl;
            getchar();
        }
    }
    return 0;
}