`
huyifan951124
  • 浏览: 82990 次
社区版块
存档分类
最新评论

NYOJ士兵杀敌2(线段树的单点更新,区间查询)

 
阅读更多

初学线段树--单点更新,区间查询

算法思路:运用递归,建完树之后,再通过递归,找到树节点的左区间端点==右区间端点&&等于你要查询的那个下标,然后更新其值,就完成了单点更新,最后区间查询时注意区间横跨树的两个节点的情况。

下面上代码:

 

#include<iostream>
#include<cstdio>
using namespace std;

typedef struct Node
{
    int value;
    int l;
    int r;

};
Node tree[1000050*4];
int a[1000050];
int n,m;
long int sum;
char str[10];
void build_tree(int v,int l,int r)
{
    tree[v].l=l;
    tree[v].r=r;
    if(l==r)
    {
        tree[v].value=a[l];
        return;
    }
    else
    {
        int mid=(l+r)/2;
        build_tree(v*2,l,mid);
        build_tree(v*2+1,mid+1,r);
        tree[v].value=tree[v*2].value+tree[v*2+1].value;
    }
}
void query(int v,int l,int r)
{
    if(tree[v].l==l&&tree[v].r==r)
    {
        sum+=tree[v].value;
        return;
    }

    int mid=(tree[v].l+tree[v].r)/2;
    if(r<=mid)
    {
        query(v*2,l,r);
    }
    else
    {
        if(l>mid)
            query(v*2+1,l,r);
        else
        {
            query(v*2,l,mid);
            query(v*2+1,mid+1,r);
        }
    }


}
void update(int v,int add,int p)
{
    if(tree[v].l==tree[v].r)
    {
        tree[v].value+=add;
        return;
    }
    int mid=(tree[v].l+tree[v].r)/2;

    if(p<=mid)
        update(v*2,add,p);
    else
        update(v*2+1,add,p);
    tree[v].value=tree[v*2].value+tree[v*2+1].value;


}
int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }

     build_tree(1,1,n);


    for(int i=0;i<m;i++)
    {
        int left=0,right=0;
        sum=0;
        scanf("%s%d%d",str,&left,&right);
        if(str[0]=='Q')
        {
            query(1,left,right);
            printf("%d\n",sum);
        }

        else
        {
            int p=left;
            int add=right;
            update(1,add,p);

        }


    }

    return 0;

}




        

 

分享到:
评论

相关推荐

    ACM在线评测系统 NYOJ 题库 离线看题网页版 nyoj

    NYOJ,全称为南阳理工学院在线评测系统(Nanyang Institute of Technology Online Judge),是为ACM(国际大学生程序设计竞赛)以及其他编程爱好者提供的一种在线编程练习平台。该系统支持用户提交代码并进行实时...

    nyoj部分ACM答案

    ### nyoj部分ACM答案解析 #### 背景与目的 本篇文章旨在解析一个针对NYOJ(网络在线裁判系统)中ACM题目解答的示例代码。该代码使用了C++语言,并且主要涉及到了回溯算法的实现。对于初学者来说,通过深入理解这段...

    NYOJ.290.DictionaryTree.zip_trie树c_字典树_高级数据结构

    字典树,也被称为Trie树或前缀树,是一种高效的数据结构,尤其适用于字符串相关的查找和插入操作。在计算机科学领域,它被广泛应用在字典、搜索引擎、自动补全功能以及IP路由等方面。Trie树的核心优势在于其能够通过...

    算法-矩形嵌套(NYOJ-16)(包含源程序).rar

    例如,如果使用平衡二叉搜索树,插入和查询的时间复杂度可以达到O(logn),而线段树则可以在O(logn)时间内处理区间更新和查询操作。 6. **实战应用**: 这类问题的解决方法不仅适用于矩形,还可以推广到其他二维...

    NYOJ题目 离线版

    NYOJ(New York Online Judge)是一个在线编程竞赛平台,主要面向ACM(国际大学生程序设计竞赛)的参与者。这个离线版包含了NYOJ的所有题目,为编程爱好者和参赛者提供了一个方便的本地化练习环境。通过爬虫技术,...

    nyoj16.rar_site:www.pudn.com

    标题中的“nyoj16.rar”可能是指一个编程竞赛或者在线判题系统(如NOIP、NYOJ)的问题编号16的题目,而“site:www.pudn.com”通常用于搜索引擎查询,表明这个压缩文件可能来源于PUDN(普渡大学电子论坛)这个网站。...

    ACM题库题库啊

    NYOJ,全称New York Online Judge,是一个在线编程竞赛平台,提供了丰富的ACM竞赛训练题目。离线版的NYOJ可能是将该平台的部分内容打包成CHM文件,方便用户在没有网络的情况下查阅和练习。这个CHM文件可能包含题目的...

    nyoj 61 传纸条(一)

    双线程动态规划问题,很值得练习。传一个ac代码,测试一下csdn的功能。

    nyoj_lvy实战开发系列《三》: 获取城市信息

    由于微信小程序没有方法可以获得当前用户所在城市的信息,所以需要调用方法来获取城市信息,用了两个方法去发送请求并返回城市信息  1. @Controller public class WechatLocationManager { private Logger logger ...

    南阳理工学院OJ第1版解题报告V1.0.pdf

    该题要求对离散化的线段进行覆盖分析,线段树是一种高效的数据结构,能够支持区间查询和更新操作,适用于此类问题。 #### 10. skiing 经典动态规划题目,旨在寻找最佳路径,这类问题通常需要建立状态转移方程,以...

    南阳理工oj stl练习ac代码

    set和map是关联容器,以红黑树实现,用于存储唯一元素并支持快速查找。 2. 迭代器: 迭代器是STL的重要概念,它像指针一样指向容器中的元素,但具有更多操作。例如,可以使用迭代器进行元素的增删查改,遍历容器,...

    nyoj_lvy实战开发系列《二》: 微信端开发:登录小程序

    这个小程序的主要目的是为了用户用微信的用户信息登录后将用户信息授权存入自己的数据库中,这样以后每次微信登录得到的code 所得到的 openid 可以在项目的数据库中查到该用户的相关信息。 在测试的过程中,需要用户...

    nyoj_lvy实战开发系列《一》:发送JSON信息,加密数据解密算法,UnionID机制说明

    前期小程序开发只进行到根据微信用户登录获取的code 去微信的API去获取到该用户的openId和session_key,到了第二阶段,老大让我重写OAuthManager的代码来实现微信小程序和微信公众号平台获取用户信息的优化,即将...

    经典动态规划 南阳104最大和

    给定一个由整数组成二维矩阵(r*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。

Global site tag (gtag.js) - Google Analytics