A Simple Problem with Integers
Description
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15
Description
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15 报告
题目大意： 一串数，“C a b c" 表示在区间[a,b]中每个数 + c
"Q a b"表示查询区间[a,b] 的和 线段树： 学习了线段树后的第一道题。这道题包含了线段树的Pushdown,Pushup,Query,Build,Update几个函数，很好地让初学者了解了线段树的用法和精髓--延迟更新，即每次更新时只是做一个标记，当要查找时才继续向下更新。还要注意的是，有些题不需要向下回溯（pushup），也不需要延迟更新（pushdown），甚至连更新都不用。但是需要根据题意改变要查找的内容和更新的内容，有的需要找最大值，有的需要找和，等等，需要随机应变。线段树能解决的问题，树状数组不一定能解决，但是树状数组能解决的，线段树一定能解决。 思路： 便不多说。上代码。
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#define L(u) (u<<1)
#define R(u) (u<<1|1)//没有分号
using namespace std;
int n,q;
long long c;
long long a[];
struct node{
int l,r;
long long add,sum;
};
char s[];
node pp[];/**数据范围**/
void pushup(int u)
{
pp[u].sum=pp[L(u)].sum+pp[R(u)].sum;
return ;
}
void pushdown(int u)
{
pp[L(u)].add+=pp[u].add;
pp[L(u)].sum+=(pp[L(u)].r-pp[L(u)].l+)*pp[u].add;
pp[R(u)].add+=pp[u].add;
pp[R(u)].sum+=(pp[R(u)].r-pp[R(u)].l+)*pp[u].add;
pp[u].add=;/*！！！*/
}
void update(int u,int left,int right,long long t)
{
if (left<=pp[u].l&&pp[u].r<=right)
{
pp[u].add+=t;
pp[u].sum+=(pp[u].r-pp[u].l+)*t;
return ;
}
pp[u].sum+=(right-left+)*t;
if (pp[u].add) pushdown(u);
int mid=(pp[u].l+pp[u].r)>>;
if (right<=mid) update(L(u),left,right,t);
else /***/if (left>mid) update(R(u),left,right,t);
else
{
update(L(u),left,mid,t);
update(R(u),mid+,right,t);
}
//pushup(u);
} void build(int u,int left,int right)
{
pp[u].l=left;
pp[u].r=right;
pp[u].add=;
if (pp[u].l==pp[u].r)
{
pp[u].sum=a[left];//*****
return ;
}
int mid=(pp[u].l+pp[u].r)>>;
build(L(u),left,mid);
build(R(u),mid+,right);
pushup(u);
}
long long query(int u,int left,int right)
{
if (left==pp[u].l&&pp[u].r==right)
return pp[u].sum;
if (pp[u].add) pushdown(u);
int mid=(pp[u].l+pp[u].r)>>;
if (right<=mid) return query(L(u),left,right);
if (left>mid) return query(R(u),left,right);
else
return (query(L(u),left,mid)+query(R(u),mid+,right));
}
int main()
{
//freopen("tree.in","r",stdin);
cin>>n>>q;
for (int i=;i<=n;i++)
scanf("%lld",&a[i]);//long long 读数
build(,,n);
for (int i=;i<=q;i++)
{
scanf("%s",s);
if (s[]=='Q')
{
int k,b;
scanf("%d%d",&k,&b);
cout<<query(,k,b)<<endl;
}
else
{
int k,b;
cin>>k>>b>>c;
update(,k,b,c);
}
} return ;
}
注意事项：1、数据范围：线段树一般定义4*n
2、#difine 的使用 function() ( ** ) 注意括号没有分号；
3、runtime error ：运行错误 long long a[i], %lld(linux) %I64d （windows)
4、模板答题 顺便抱怨一下，poj的评测系统太慢了，waiting了好久.......