简单题
【题目描述】：
给你N个整数A1,A2,….,AN，你可以进行两种操作：一种把一给定区间的每个数是增加一个值；另一种是计算某一给定区间的数字的和。
【输入格式】：
第一行包含两个整数N和Q.1<=N,Q<=100000
第二行包含N个整数，是A1,A2,….,AN的初始值。-1000000000<=Ai<=1000000000
接下来Q行，描述操作。
“C a b c”表示把Aa,Aa+1,….Ab都增加c，-10000<=c<=10000。
“Q a b”表示询问Aa,Aa+1,….,Ab的和。
【输出格式】：
对于每个询问输出对应的和，每行一个。
【样例输入】：
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
【样例输出】：
4
55
9
15
【数据说明】：
30%数据 N,Q<=10000
程序1和程序2都是线段树，只是写法有点不太相同，程序2跑得会更快一些：
程序1：
Program Simple_Mpq;
type data=record
sum:int64;
add:int64;
end;
Const Maxn=1 shl (trunc(ln(100000)/ln(2))+2);
var
sum:int64;
n,m,add:longint;
a:array[1..100000] of longint;
tree:array[1..Maxn+1] of data;
procedure Build(x,y,len:longint);
var
m:longint;
begin
if x=y then
begin
read(x);
tree[len].sum:=x;
tree[len].add:=0;
exit;
end;
m:=(x+y) div 2;
build(x,m,len*2);
build(m+1,y,len*2+1);
tree[len].sum:=tree[len*2].sum+tree[len*2+1].sum;
end;
procedure init;
var
x,i:longint;
begin
readln(n,m);
Build(1,n,1);
readln;
end;
function Min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
function Max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure Change(x,y,l,r,len:longint);
var
m:longint;
begin
if (l>r) then exit;
if (x=l) and (y=r) then
begin
tree[len].sum:=tree[len].sum+(y-x+1)*add;
tree[len].add:=tree[len].add+add;
exit;
end;
m:=(x+y) div 2;
Change(x,m,l,min(m,r),len*2);
Change(m+1,y,max(m+1,l),r,len*2+1);
tree[len].sum:=tree[len*2].sum+tree[len*2+1].sum+tree[len].add*(y-x+1);
end;
procedure Count(x,y,l,r,len:longint);
var
tmp:int64;
m:longint;
begin
if (l>r) then exit;
if (x=l) and (y=r) then
begin
sum:=sum+tree[len].sum;
exit;
end;
m:=(x+y) div 2;
Count(x,m,l,min(m,r),len*2);
Count(m+1,y,max(m+1,l),r,len*2+1);
sum:=sum+tree[len].add*(r-l+1);
end;
procedure Main;
var
ch:char;
i,left,right:longint;
begin
for i:=1 to m do
begin
read(ch);
if ch='C' then
begin
readln(left,right,add);
Change(1,n,left,right,1);
end else
begin
sum:=0;
readln(left,right);
Count(1,n,left,right,1);
writeln(sum);
end;
end;
end;
begin
assign(input,'simple.in'); reset(input);
assign(output,'simple.out'); rewrite(output);
init;
Main;
close(input); close(output);
end.
程序2：
Program Simple_Mpq;
type data=record
sum,add:int64;
end;
Const Maxn=1 shl (trunc(ln(100000)/ln(2)+2));
var
n,m,left,right,add:longint;
tree:array[1..Maxn] of data;
procedure Build(x,y,len:longint);
var
m:longint;
begin
if x=y then
begin
read(x);
tree[len].sum:=x;
tree[len].add:=0;
exit;
end;
m:=(x+y) div 2;
Build(x,m,len*2);
Build(m+1,y,len*2+1);
tree[len].sum:=tree[len*2].sum+tree[len*2+1].sum;
end;
procedure init;
begin
readln(n,m);
Build(1,n,1);
readln;
end;
procedure Change(x,y,len:longint);
var
m:longint;
begin
if (x>right) or (left>y) then exit;
if (x>=left) and (right>=y) then
begin
tree[len].sum:=tree[len].sum+(y-x+1)*add;
inc(tree[len].add,add);
exit;
end;
m:=(x+y) div 2;
Change(x,m,len*2);
Change(m+1,y,len*2+1);
tree[len].sum:=tree[len*2].sum+tree[len*2+1].sum+tree[len].add*(y-x+1);
end;
function Min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
function Max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function Count(x,y,len:longint):int64;
var
m:longint;
begin
if (x>right) or (left>y) then exit(0);
if (x>=left) and (right>=y) then exit(tree[len].sum);
m:=(x+y) div 2;
Exit(Count(x,m,len*2)+Count(m+1,y,len*2+1)+tree[len].add*(Min(y,right)-Max(x,left)+1));
end;
procedure Main;
var
ch:char;
i:longint;
begin
for i:=1 to m do
begin
read(ch);
if ch='C' then
begin
readln(left,right,add);
Change(1,n,1);
end else
begin
readln(left,right);
writeln(Count(1,n,1));
end;
end;
end;
begin
assign(input,'simple.in'); reset(input);
assign(output,'simple.out'); rewrite(output);
init;
Main;
close(input); close(output);
end.