当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

[线段树]hdoj 1166:敌兵布阵

发表于: 2012-10-21   作者:暴风雪   来源:转载   浏览次数:
摘要: 大致题意:    给出一个n长度的数组,在线的实现改变某个值,查询一个区间和的功能。   大致思路:    基础线段树。。G++死活过不去,郁闷,用c++水过去了     #include<iostream> #include<cstring> #include<cstdio>

大致题意:
    给出一个n长度的数组,在线的实现改变某个值,查询一个区间和的功能。

 

大致思路:
    基础线段树。。G++死活过不去,郁闷,用c++水过去了

 

 

#include<iostream>
#include<cstring>
#include<cstdio>
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()
{
    char str[10];
    int cas,i,j,a,b,c,n,t=0;
    cin>>cas;
    while(cas--)
    {
        cin>>n;
        for(i=1;i<=n;i++)
        {
            //cin>>num[i];
            scanf("%d",&num[i]);
        }
        printf("Case %d:\n",++t);
        BuildTree(1,n,1);
        while(cin>>str&&str[0]!='E')
        {
            if(str[0]=='Q')
            {
                cin>>a>>b;
                //cout<<query(a,b,1)<<endl;
                a=query(a,b,1);
                printf("%d\n",a);
            }
            if(str[0]=='A')
            {
                //cin>>a>>b;
                scanf("%d%d",&a,&b);
                updata(a,b,1);
            }
            if(str[0]=='S')
            {
                scanf("%d%d",&a,&b);
                updata(a,-b,1);
            }
        }
    }
    return 0;
}

[线段树]hdoj 1166:敌兵布阵

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
经验: cout 特别慢 如果要求速度 全部用 printf !!! 在学习线段树 内容来自:http://www.cnblogs.c
题意: 同上 题解: 抓着这题作死的搞~~是因为今天练习赛的一道题.SPOJ KQUERY.直到我用最后一种树状
线段树在一些acm题目中经常见到,这种数据结构主要应用在计算几何和地理信息系统中。下图就为一个线
定义 线段树是一种的二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应
树结构的基本思想是分割。普通二叉搜索树是按对象来进行划分,效果往往和数据结构内对象有关;而线
线段树的构造思想 线段树是一棵二叉树,树中的每一个结点表示了一个 区间[a,b]。每一个叶子节点表示
线段树(interval tree) 是把区间逐次二分得到的一树状结构,它反映了包括归并排序在内的很多分治算
从简单说起,线段树其实可以理解成一种特殊的二叉树。但是这种二叉树较为平衡,和静态二叉树一样,
原文转自:http://blog.csdn.net/dgq8211/article/details/7407753 先从书上把定义抄下来: 一棵二
学习了几天线段树,做了几道线段树题,挺有成就感的\(^o^)/~ POJ2528 Mayor's posters 线段树入门题
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号