首页 > 代码库 > poj3468（线段树）

poj3468（线段树）

2024-11-12 07:47:02   203人阅读

 

题目连接：http://poj.org/problem?id=3468

线段树功能:update:成段增减 query:区间求和。

分析：需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候。

 

技术分享
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define LL long long#define M 1000000000#define maxn 111111#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;LL sum[maxn<<2];LL col[maxn<<2];void Pushup(int rt){    sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void Pushdown(int rt,int m){    if(col[rt])    {        col[rt<<1]+=col[rt];        col[rt<<1|1]+=col[rt];        sum[rt<<1]+=col[rt]*(m-(m>>1));        sum[rt<<1|1]+=col[rt]*(m>>1);        col[rt]=0;    }}void build(int l,int r,int rt){    col[rt]=0;    if(l==r)    {        scanf("%lld",&sum[rt]);        return;    }    int m=(l+r)>>1;    build(lson);    build(rson);    Pushup(rt);}void update(int L,int R,int c,int l,int r,int rt){    if(L<=l&&r<=R)    {        col[rt]+=c;        sum[rt]+=(LL)(r-l+1)*c;        return;    }    Pushdown(rt,r-l+1);    int m=(l+r)>>1;    if(L<=m)update(L,R,c,lson);    if(m<R)update(L,R,c,rson);    Pushup(rt);}LL query(int L,int R,int l,int r,int rt){    if(L<=l&&r<=R)        return sum[rt];    Pushdown(rt,r-l+1);    int m=(r+l)>>1;    LL res=0;    if(L<=m)res+=query(L,R,lson);    if(R>m)res+=query(L,R,rson);    return res;}int main(){    int n,m;    char op[10];    while(scanf("%d%d",&n,&m)>0)    {        build(1,n,1);        while(m--)        {            int a,b,c;            scanf("%s",op);            if(op[0]==‘Q‘)            {                scanf("%d%d",&a,&b);                printf("%lld\n",query(a,b,1,n,1));            }            else            {                scanf("%d%d%d",&a,&b,&c);                update(a,b,c,1,n,1);            }        }    }    return 0;}
View Code

 

poj3468（线段树）


联系
我们