POJ 3468 线段树 区间更新区间查询

题意:给出一段数列,任意区间加上一个整数v,任意区间查询。给出N个数,Q次操作。

线段树的题,延迟指针不更新到底就行了。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 100005
long long sum[maxn<<2],col[maxn<<2];
void build(int rt,int l,int r)
{
    col[rt]=0;
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int L,int R,long long c,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        col[rt]+=c;
        sum[rt]+=(long long)(r-l+1)*c;
        return;
    }
    if(col[rt]!=0)
    {
        int m=(r-l+1);
        col[rt<<1]+=col[rt],col[rt<<1|1]+=col[rt];
        sum[rt<<1]+=(long long)(m-(m>>1))*col[rt];
        sum[rt<<1|1]+=(long long)(m>>1)*col[rt];
        col[rt]=0;
    }
    int mid=(l+r)>>1;
    if(mid>=L)
        update(L,R,c,l,mid,rt<<1);
    if(mid<R)
        update(L,R,c,mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
long long query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return sum[rt];
    if(col[rt]!=0)
    {
        int m=(r-l+1);
        col[rt<<1]+=col[rt],col[rt<<1|1]+=col[rt];
        sum[rt<<1]+=(long long)(m-(m>>1))*col[rt];
        sum[rt<<1|1]+=(long long)(m>>1)*col[rt];
        col[rt]=0;
    }
    int mid=(l+r)>>1;
    long long ret=0;
    if(mid>=L)
        ret+=query(L,R,l,mid,rt<<1);
    if(mid<R)
        ret+=query(L,R,mid+1,r,rt<<1|1);
    return ret;
}
int main()
{
    int n,q,a,b;
    long long v;
    char c[2];
    while(~scanf("%d%d",&n,&q))
    {
        build(1,1,n);
        while(q--)
        {
            scanf("%s%d%d",c,&a,&b);
            if(c[0]=='Q')
                printf("%lld\n",query(a,b,1,n,1));
            else
                scanf("%lld",&v),update(a,b,v,1,n,1);
        }
    }
    return 0;
}
时间: 2024-12-22 12:28:27

POJ 3468 线段树 区间更新区间查询的相关文章

【转】POJ 3264 线段树解法

每个算法都是数学家或者计算机学家多年研究的结果,不是我自己臆造的,所以学习一个新算法的最佳方法还是看写的好的代码. 按照惯例,我就粘贴一个网上写的很好的帖子... 原文地址:http://ip96cns.blog.163.com/blog/static/17009519220112525029459/ 线段树的查找:(感谢高手指点,虽然只是一点却让我把线段树的内容理顺了)这里是我的一些总结吧           一个线段树的结点表示一个区间,同时结点中保存所需要的信息.          如果询

线段树-区间延迟修改-zoj-1610

Count the Colors Description Painting some colored segments on a line, some previously painted segments may be covered by  some the subsequent ones.  Your task is counting the segments of different colors you can see at last. Input The first line of 

HDU 1166 线段树单点更新

第一行一个整数T,表示有T组数据.每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地,接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50).接下来每行有一条命令,命令有4种形式:(1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30);(3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人

HDU 1394 线段树单点更新求逆序数

题意:给出含有0 ~n-1 N个数组成的序列,有N次操作,每次把第一个数放到数列的最后,问这几次数列操作中最小的逆序数的值. 单点更新就可以,每一输入一个数,先查询有几个比这个数大的,再将这个值插入线段树中. #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 5005 struct node { i

[算法系列之二十三]线段树(Interval Tree)

一 背景 在信息学竞赛中,我们经常会碰到一些跟区间有关的问题,比如给一些区 间线段求并区间的长度,或者并区间的个数等等.这些问题的描述都非常简单,但是通常情况下数据范围会非常大,而朴素方法的时间复杂度过高,导致不能在规定时间内得到问题的解.这时,我们需要一种高效的数据结构来处理这样的问题,在本文中,我们介绍一种基于分治思想的数据结构--线段树. 二 简介 线段树是一种二叉树形结构,属于平衡树的一种.它将线段区间组织成树形的结构,并用每个节点来表示一条线段.一棵[1,10)的线段树的结构如图1.1

高级数据结构中,线段树问题

问题描述 高级数据结构中,线段树问题 高级数据结构中,线段树可以处理很多区间问题,但是这些数据结构在现实项目中用 得多吗?还是这只是存在于竞赛中而已.如果现实项目中有用到,能不能举个例子? 解决方案 我曾级听过一个大牛说,线段树用得很少,基本没有用到... 解决方案二: 高级数据结构 - 线段树(1)数据结构--线段树--区间涂色问题高级数据结构 - 线段树(2)

HDU 1698 线段树成段更新

题意:线段树成段更新,最后查询全区间. #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 100005 int node[maxn<<2],col[maxn<<2]; void build(int rt,int l,int r) { col[rt]=0,node[rt]

《程序设计解题策略》——1.3 利用线段树解决区间计算问题

1.3 利用线段树解决区间计算问题 在现实生活中,我们经常遇到与区间有关的问题,例如,记录一个区间的最值(最大或最小值)和总量,并在区间的插入.删除.修改中维护这些最值和总量:再如,统计若干矩形并的面积.线段树拥有良好的树形二分特征,我们可以从其定义和结构中发现,在线段树的基础上完成这些问题的计算操作,是十分简捷和高效的.1.3.1 线段树的基本概念 一棵二叉树,记为T(a,b),参数a.b表示该节点表示区间[a,b].区间的长度b-a记为L.递归定义T[a,b]: 若区间长度L>1:区间[a,

poj 2528 Mayor&#039;s posters(线段树+离散化)

/* poj 2528 Mayor's posters 线段树 + 离散化 离散化的理解: 给你一系列的正整数, 例如 1, 4 , 100, 1000000000, 如果利用线段树求解的话,很明显 会导致内存的耗尽.所以我们做一个映射关系,将范围很大的数据映射到范围很小的数据上 1---->1 4----->2 100----->3 1000000000----->4 这样就会减少内存一些不必要的消耗 建立好映射关系了,接着就是利用线段树求解 */ #include<ios