51Nod-1081 子段求和_51nod 1081-程序员宅基地

技术标签: 线段树  51NOD  51Nod-基础题  

题目
给出一个长度为N的数组,进行Q次查询,查询从第i个元素开始长度为l的子段所有元素之和。
例如,1 3 7 9 -1,查询第2个元素开始长度为3的子段和,1 {3 7 9} -1。3 + 7 + 9 = 19,输出19。
Input
第1行:一个数N,N为数组的长度(2 <= N <= 50000)。
第2 至 N + 1行:数组的N个元素。(-10^9 <= N[i] <= 10^9)
第N + 2行:1个数Q,Q为查询的数量。
第N + 3 至 N + Q + 2行:每行2个数,i,l(1 <= i <= N,i + l <= N)
Output
共Q行,对应Q次查询的计算结果。
Input示例
5
1
3
7
9
-1
4
1 2
2 2
3 2
1 5
Output示例
4
10
16
19
题解:线段树的区间求和模板题。
AC代码:
/*
* @Author: 王文宇
* @Date:   2017-10-23 15:31:18
* @Last Modified by:   王文宇
* @Last Modified time: 2017-10-23 15:35:18
*/
#include<iostream>
using namespace std;
#define maxn 50005
int n,m;
struct node
{
    int l,r;
    long long sum;
}E[maxn*4];
void build(int l,int r,int x)
{
    E[x].l=l;
    E[x].r=r;
    if(l==r)
    {
        cin>>E[x].sum;
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    E[x].sum=E[x*2].sum+E[x*2+1].sum;
}
long long query(int l,int r,int x)
{
    int ll=E[x].l;
    int rr=E[x].r;
    if(ll>=l&&rr<=r)return E[x].sum;
    int mid = (ll+rr)/2;
    if(mid>=r)return query(l,r,x*2);
    else if(mid<l)return query(l,r,x*2+1);

    else return query(mid+1,r,x*2+1)+query(l,mid,x*2);
}
int main()
{
    cin>>n;
    build(1,n,1);
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        cout<<query(x,x+y-1,1)<<endl;
    }
    return 0;
}



版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sortmin/article/details/78319400

智能推荐

DVWA—【文件包含漏洞】实验详解_<?php // the page we wish to display $file = $_get-程序员宅基地

文章浏览阅读1.4k次,点赞3次,收藏3次。LOW实验关键代码<?php $file = $_GET['page'];//The page we wish to display?>这是一个典型的在动态网页中的用法,就像注我上一篇文章【文件包含漏洞原理】所讲,写入我们想要显示的页面。这里就是对用户的输入完全信任,因此就导致可以包含任意页面。程序员在写程序的时候要站在不安全的角度上,而不是用户的角度上,这是从网站安全的角度来说。实验:接下来通过文件包含漏洞,查看位于根目录下的1.txt文件的内容,同过这两个实验对比总结远_<?php // the page we wish to display $file = $_get[ 'page' ]; // input valid</div>

cordova打包vue项目为app_cordova 打包出来是 aap格式-程序员宅基地

文章浏览阅读4k次。一、创建cordova项目1、创建项目前提条件(1)node.js详细安装步骤可参考node.js官网:https://nodejs.org/en/下载安装成功后,在命令窗口中输入npm -v查看是否成功(2)JDK在官网下载安装:https://www.oracle.com/index.html并配置环境变量(重要)成功后,在命令窗口输入java 和javac。出现类似信息则表示安装成功。(3)..._cordova 打包出来是 aap格式

bootstrap.yml不支持logback.xml或者logback-spring.xml配置_${nacos_host:127.0.0.1}-程序员宅基地

文章浏览阅读2k次。一、背景最近一个springboot单体架构的项目改造为springcloud微服务项目的过程中,为了使用nacos的配置中心,同时又想本地开发环境不依赖于nacos,就把application.yml改造成了bootstrap.yml,同时多环境配置application-dev.yml也改为了bootstrap-dev.yml。初始环境配置文件结构如下:二、logback.xml不生效问题微服务改造完成后,本地开发环境logback.xml不生效,最明显的特征是配置的SQL打印没有了,而服务器_${nacos_host:127.0.0.1}

Android入门项目(六)Android的wifi开发,2024年最新快手面试java-程序员宅基地

文章浏览阅读616次,点赞28次,收藏13次。这里我特地整理了一份《Android开发核心知识点笔记》,里面就包含了自定义View相关的内容除了这份笔记,还给大家分享Android学习PDF+架构视频+面试文档+源码笔记,高级架构技术进阶脑图、Android开发面试专题资料,高级进阶架构资料这几块的内容。非常适合近期有面试和想在技术道路上继续精进的朋友。分享上面这些资源,希望可以帮助到大家提升进阶,如果你觉得还算有用的话,不妨把它们推荐给你的朋友~喜欢本文的话,给我点个小赞、评论区留言或者转发支持一下呗~

推荐一款Gin+Vue+ElementUI实现的智慧城市后台管理系统_vue智慧城市项目-程序员宅基地

文章浏览阅读496次。是一款基于Golang、Gin、Xorm、Vue、ElementUI、MySQL等技术栈开发平台框架,拥有完善的(RBAC)权限架构和基础核心管理模块,为了缩短研发周期,系统框架集成了代码生成器,内置平台自定义研发的模板引擎,可以一键CRUD生成整个模块的全部代码,本框架为一站式系统框架开发平台,可以帮助开发者提升开发效率、降低研发成本,同时便于后期的系统维护升级。......_vue智慧城市项目

单片机应用案例大全-900套(保持更新)_单片机的实际应用案例-程序员宅基地

文章浏览阅读4.6w次,点赞85次,收藏1.2k次。1 F103F40751单片机CS5463驱动.zip.zip 2 用单片机实现声级计智能.zip 3 单片机元件库.zip.zip 4 单片机-基于单片机控制的交通灯毕业设计资料.zip 5 单片机-智能台灯设计资料.zip 6 单片机-应用电子、继电线路设计资料.zip 7 单片机-基于单片机的作息时间控制钟系统资料.zip 8 单片机-交通控制器设计资料.zip 9 单片机-智能温度报警系统设计资料.zip 10_单片机的实际应用案例

随便推点

云计算虚拟化与云平台如何对接安可领域?-程序员宅基地

文章浏览阅读4.2k次。在本月举办的“2018四季度安全可靠技术和应用研讨会”上,作为安可联盟成员,云宏隆重发布了“全融合安可云”解决方案,得到了工信部、广东省领导的高度好评以及与会联盟单位的高度关注。在信息化发展的浪潮中,云计算支撑着相关领域业务的高速发展,云计算关键技术更是新一代信息技术领域不可或缺的一部分。安可领域要实现创新发展,采用安全可靠云计算方案便显得尤为关键。云宏安可云解决方案,即为..._安可云

mybatis-plus实体类中字段和数据库中字段名不对应解决办法_mybatis-plus 数据库名与实体不一样-程序员宅基地

文章浏览阅读1.3w次,点赞10次,收藏11次。在使用mybatis或者mybatis-plus时候,有些时候会出现数据库的字段名和实体类的字段名不一致的情况,如果运行那么这个字段就会无法进行自动映射而报错。这里就以我的数据库name字段名和这里的实体类的u_name字段名为例。解决办法有以下三种方法一:将数据库中的字段和实体类中的字段名修改成一样的名字方法二:如果是自定以mapper.xml文件中手写的sql查询语句,可以给字段起一个别名例如这里就可以写成select name as u_name from…方法三:使用注解._mybatis-plus 数据库名与实体不一样

谁也不服,只服Alibaba技术官,Kafka的精髓浓缩进一本“限量笔记”里_alibaba kafka不是中国的嘛-程序员宅基地

文章浏览阅读101次。前言分布式,是程序员必备技能之一,在面试过程中属于必备类的,在工作中更是会经常用到。而Kafka是一个分布式的基于发布订阅的消息队列,目前它的魅力是无穷的,对于Kafka的奥秘,还需要我们细细去探寻。要谈对Kafka有多熟悉,我相信还是阿里的大佬们最有发言权,所以今天分享的内容,就是Alibaba内部供应的“限量笔记”,关于Kafka的精髓全部写在这里面了,不得不感叹:不愧是Alibaba的技术官啊,真的服了!关于这份Kafka限量笔记,我只能在文章中展示部分的章节内容和核心截图,如果你需要完_alibaba kafka不是中国的嘛

LeetCode第131题—分隔回文串—Python实现_python 131leetcode-程序员宅基地

文章浏览阅读427次。title: LeetCode No.131categories:OJLeetCodetags:ProgramingLeetCodeOJLeetCode第131题—分隔回文串昨天端午鸽了塞自己代码的开源仓库:click here 欢迎Star和Fork ????题目描述给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。示例 1:输入:s = "aab"输出:[["a",_python 131leetcode

Mysql-使用avg()与if()函数计算正确率_avg(if())-程序员宅基地

文章浏览阅读2.4k次。计算上表中不同难度的题目答题准确率。selectq.difficult_level,avg(if(q.result="right",1,0)) correct_rate#此处平均值计算结果=正确的题目数量/总答题数量from question_detail qgroup by q.difficult_level_avg(if())

由于找不到MSVCR100.dll,msvcr120.dll无法继续执行代码_msvcr20dll-程序员宅基地

文章浏览阅读3.8k次。转自个人博客:https://www.tanchengjin.com/article/108这是由于wamp依赖Microsoft Visual C++ 2010(VC2010运行库)所导致出现MSVCR110.dll错误msvcp、msvcr、vcomp140.dll属于VC++2015版msvcp、msvcr、vcomp120.dll属于VC++2013版..._msvcr20dll

推荐文章

热门文章

相关标签