Poj 3468 A Simple Problem with Integers 线段树

题意

你有n个数。现在有两种操作，一种是使区间A到B上每个数加C，另一个是求区间A到B之间数的和。

题解思路

这个题目应该使用线段树来进行求解，至于为什么不能单个求解呢，因为会超时，使用前缀和的话，无法满足修改的要求，线段树很好的解决了这个问题。

线段树的讲解我就不写了，这个太麻烦了（别问，问就是懒），这里推荐一个博客，线段树详解很好，我就是看这个学会的，这个题也是模板题，可以学会敲一敲。

我的代码

没有使用结构体，最简单的那种

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
ll sum[maxn<<2], lazy[maxn<<2];
int a[maxn];
int n,m;
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    return ;
}
void build(int rt, int l, int r)
{
    lazy[rt]=0; //默认需要初始化为0 
    if(l==r)
    {
        sum[rt]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
    pushup(rt);
}
void pushdown(int rt, int ln, int rn)
{
    int r=rt<<1, l=rt<<1|1;
    lazy[r]+=lazy[rt];
    sum[r]+=lazy[rt]*ln;
    
    lazy[l]+=lazy[rt];
    sum[l]+=lazy[rt]*rn;
    
    lazy[rt]=0;

}
void regiondup(int rt, int l, int r, int L, int R, int x)
{
    if(L<=l && r<=R)
    {
        sum[rt]+=(r-l+1)*x;
        lazy[rt]+=x;
        return ;    
    }
    int mid=(l+r)>>1;
    if(lazy[rt]!=0) pushdown(rt, mid-l+1, r-mid);
    if(L<=mid) regiondup(rt<<1, l, mid, L, R, x);
    if(R>mid) regiondup(rt<<1|1, mid+1, r, L, R, x);
    pushup(rt);
}
ll query(int rt, int l, int r, int L, int R)
{
    if(L<=l && r<=R)
    {
        return sum[rt];
    }
    int mid=(l+r)>>1;
    if(lazy[rt]!=0)pushdown(rt, mid-l+1, r-mid);
    ll ans=0;
    if(L<=mid) ans+=query(rt<<1, l, mid, L, R);
    if(R>mid) ans+=query(rt<<1|1, mid+1, r, L, R);
    return ans;
}

int main()
{
    int L, R, c;
    char s[4];
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        for(int i=1; i<=n; i++)
        {
            scanf("%d", &a[i]);
        }
        build(1, 1, n);
        for(int i=1; i<=m; i++)
        {
            scanf("%s", s);
            if(s[0]=='Q')
            {
                scanf("%d%d", &L, &R);
                printf("%lld\n", query(1, 1, n, L, R));
            }
            else{
                scanf("%d%d%d", &L, &R, &c);
                regiondup(1, 1, n, L, R, c);
            }
        }
    }
    return 0;
}

END

Poj 3468 A Simple Problem with Integers 线段树

原文：https://www.cnblogs.com/alking1001/p/11307868.html