【POJ 3468】A Simple Problem with Integers【线段树】

本文主要是介绍【POJ 3468】A Simple Problem with Integers【线段树】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：http://poj.org/problem?id=3468
给出一个初始数列，有两种操作：

$Q\ x\ y$ ，输出这个数列 $x$ 到 $y$ 之间的数字和。
$C\ x\ y\ z$ ，将这个数列的 $x$ 到 $y$ 之间的数加上 $z$

思路：

很裸的线段树。和模板相似度100%。
模板

代码：

#include <iostream>
#include <cstdio>
using namespace std;int n,m,x,y;
long long num[100001],z;
char c;struct node 
{int l,r;long long lazy,num;
}tree[300001];void make(int x)  //建树
{if (tree[x].r<=tree[x].l) return;int mid=(tree[x].l+tree[x].r)/2;tree[x*2].l=tree[x].l;tree[x*2].r=mid;tree[x*2+1].l=mid+1;tree[x*2+1].r=tree[x].r;make(x*2);make(x*2+1);return;
}long long lazy(int x)
{return tree[x].lazy*(tree[x].r-tree[x].l+1);
}void pushdown(int x)  //下传
{if (tree[x].lazy)  //有标记{tree[x*2].lazy+=tree[x].lazy;tree[x*2+1].lazy+=tree[x].lazy;tree[x].num+=lazy(x);tree[x].lazy=0;}return;
}void add(int x,int l,int r,long long k)  //更改（C操作）
{if (l==tree[x].l&&r==tree[x].r)  //找到{tree[x].lazy+=k;  //标记return;}if (tree[x].r<=tree[x].l) return;pushdown(x);int mid=(tree[x].l+tree[x].r)/2;if (r<=mid){add(x*2,l,r,k);tree[x].num=tree[x*2].num+tree[x*2+1].num+lazy(x*2)+lazy(x*2+1);return;}if (l>mid){add(x*2+1,l,r,k);tree[x].num=tree[x*2].num+tree[x*2+1].num+lazy(x*2)+lazy(x*2+1);return;}add(x*2,l,mid,k);add(x*2+1,mid+1,r,k);tree[x].num=tree[x*2].num+tree[x*2+1].num+lazy(x*2)+lazy(x*2+1);return;
}long long find(int x,int l,int r)  //查找（Q操作）
{if (tree[x].l==l&&tree[x].r==r)return lazy(x)+tree[x].num;if (tree[x].r<=tree[x].l) return 0;int mid=(tree[x].l+tree[x].r)/2;pushdown(x);if (r<=mid) return find(x*2,l,r);if (l>mid) return find(x*2+1,l,r);return find(x*2,l,mid)+find(x*2+1,mid+1,r);
}int main()
{scanf("%d%d",&n,&m);tree[1].l=1;tree[1].r=n;make(1);for (int i=1;i<=n;i++){scanf("%lld",&num[i]);num[i]+=num[i-1];} for (int i=1;i<=m;i++){cin>>c;if (c=='C'){scanf("%d%d%lld",&x,&y,&z);add(1,x,y,z);}else{scanf("%d%d",&x,&y);printf("%lld\n",find(1,x,y)+num[y]-num[x-1]);}}return 0;
}