延迟计算，具体思路就是，每次插入一个数字时，没必要把数字一直插入到叶子节点，只要有适合的范围就插入到这个范围中，用一个增量记录它，当下一次若有询问时，这个范围若刚好适合询问的范围，就直接把原来这个节点的值加上增量乘以范围，再加到SUM中，就可以了，若这个节点的范围不适合查询的范围的话，就要查询它的子节点了，呢么这时候再把这个增量传递给它的子节点，这样在时间上效率就会比较高了。
提交时，G++跟C++时间不一样
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
Hint
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100010;
__int64 n,m,num[maxn];
struct node
{
int x,y;
__int64 add,sum;
//add记录增量信息，sum记录总量
}nodes[maxn*4];
void build(int left,int right,int id)
{
nodes[id].x=left;
nodes[id].y=right;
nodes[id].add=0;
if(left==right)
{
nodes[id].sum=num[left];
return;
}
int mid=(nodes[id].x+nodes[id].y)>>1;
build(left,mid,id<<1);
build(mid+1,right,id<<1|1);
nodes[id].sum=nodes[id<<1].sum+nodes[id<<1|1].sum;
}
void update(int left,int right,int nn,int id)
{
if(nodes[id].x==left&&nodes[id].y==right)
{
nodes[id].add+=nn;
return ;
}
nodes[id].sum+=(right-left+1)*nn;
int mid=(nodes[id].x+nodes[id].y)>>1;
if(mid>=right)
update(left,right,nn,id<<1);
else if(mid<left)
update(left,right,nn,id<<1|1);
else
{
update(left,mid,nn,id<<1);
update(mid+1,right,nn,id<<1|1);
}
}
__int64 query(int left,int right,int id)
{
if(nodes[id].x==left&&nodes[id].y==right)
{
return nodes[id].sum+nodes[id].add*(right-left+1);
}
else
{
nodes[id<<1].add+=nodes[id].add;
nodes[id<<1|1].add+=nodes[id].add;
nodes[id].sum+=nodes[id].add*(nodes[id].y-nodes[id].x+1);
nodes[id].add=0;
}
int mid=(nodes[id].x+nodes[id].y)>>1;
if(mid>=right)
return query(left,right,id<<1);
else if(mid<left)
return query(left,right,id<<1|1);
else
{
return query(left,mid,id<<1)+query(mid+1,right,id<<1|1);
}
}
int main()
{
int i,j,a,b,aa,bb,c;
char ch[2];
while(scanf("%I64d%I64d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%I64d",&num[i]);
}
build(1,n,1);
while(m--)
{
scanf("%s",ch);
if(ch[0]=='C')
{
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,1);
}
else
{
scanf("%d%d",&aa,&bb);
printf("%I64d\n",query(aa,bb,1));
}
}
}
}