POJ - 3468 A Simple Problem with Integers（线段树，区间修改查询）

POJ - 3468 A Simple Problem with Integers

树状数组写法

线段树写法

#include<cstdio>typedef long long LL;
const int N = 100010;int w[N];
int n,m;struct tree
{
    int l,r,len;LL sum,lazy;
}tr[N*4];void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}void pushdown(int u)
{
    if(tr[u].lazy){
    tr[u<<1].lazy+=tr[u].lazy;tr[u<<1|1].lazy+=tr[u].lazy;tr[u<<1].sum+=tr[u<<1].len*tr[u].lazy;tr[u<<1|1].sum+=tr[u<<1|1].len*tr[u].lazy;tr[u].lazy=0;}
}void build(int u,int l,int r)
{
    if(l==r) tr[u]={
    l,r,r-l+1,w[l]};else{
    tr[u]={
    l,r,r-l+1};int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}void update(int u,int l,int r,LL d)
{
    if(tr[u].l>=l&&tr[u].r<=r){
    tr[u].sum+=tr[u].len*d;tr[u].lazy+=d;}else{
    pushdown(u);int mid=tr[u].l+tr[u].r>>1;if(l<=mid) update(u<<1,l,r,d);if(r>mid) update(u<<1|1,l,r,d);pushup(u);}
}LL query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;else{
    pushdown(u);int mid=tr[u].l+tr[u].r>>1;LL res=0;if(l<=mid) res=query(u<<1,l,r);if(r>mid) res+=query(u<<1|1,l,r);return res;}
}int main()
{
    scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&w[i]);build(1,1,n);char op[2];int l,r,d;for(int i=1;i<=m;i++){
    scanf("%s",&op);if(*op=='Q'){
    scanf("%d%d",&l,&r);printf("%lld\n",query(1,l,r));} else{
    scanf("%d%d%d",&l,&r,&d);update(1,l,r,d);}}return 0;
}