線段樹的成段更新
Time Limit: 5000MS Memory Limit: 131072K
Total Submissions: 38010 Accepted: 11017
Case Time Limit: 2000MS
Description
對於數列 A1, A2, ... , AN. 你要進行2個操作：將一個區間的數同加上某個數，輸出一段區間的和。
Input www.2cto.com
第一行2個整數表示數列長度和操作次數. 1 ≤ N,Q ≤ 100000.
第二行為數列 A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
接下來的Q行操作：
"C a b c" 表示將 Aa, Aa+1, ... , Ab.加上c. -10000 ≤ c ≤ 10000.
"Q a b" 輸出區間[a,b]的和。
Output
輸出所有詢問的答案，每行1個。
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
longint會爆的。
Source
POJ Monthly--2007.11.25, Yang Yi
顯然這題是線段樹。
但是我之前習慣的nowl和nowr似乎太費解了（以致於我自己都要想半天）
回去看看其它人咋寫……
[delphi]
Program poj3468;
const
maxn=100000;
maxq=100000;
var
n,m,i,j,k:longint;
lazy,t:array[1..maxn*8] of int64;
c:char;
Procedure pushup(root:longint);
begin
t[root]:=t[root*2]+t[root*2+1];
end;
Procedure build(l,r,root:longint);
var
m:longint;
begin
if (l=r) then
begin
read(t[root]);
exit;
end;
m:=(l+r) shr 1;
build(l,m,root*2);
build(m+1,r,root*2+1);
pushup(root);
end;
Procedure Pushdown(l,r,root:longint);
var
m:longint;
begin
m:=(l+r) shr 1;
if (lazy[root]=0) then exit;
inc(lazy[root shl 1],lazy[root]);
inc(lazy[root shl 1+1],lazy[root]);
inc(t[root shl 1],lazy[root]*(m-l+1));
inc(t[root shl 1+1],lazy[root]*(r-(m+1)+1));
lazy[root]:=0;
end;
Procedure update(l,r,nowl,nowr,root,cost:longint);
var
m:longint;
begin
if (l<=nowl) and (nowr<=r) then
begin
inc(lazy[root],cost);
inc(t[root],(nowr-nowl+1)*cost);
exit;
end;
pushdown(nowl,nowr,root);
m:=(nowl+nowr) shr 1;
if (l<=m) then update(l,r,nowl,m,root*2,cost);
if (m+1<=r) then update(l,r,m+1,nowr,root*2+1,cost);
pushup(root);
end;
function query(l,r,nowl,nowr,root:longint):int64;
var
m:longint;
res:int64;
begin
if (l<=nowl) and (nowr<=r) then
begin
exit(t[root]);
end;
pushdown(nowl,nowr,root);
m:=(nowl+nowr) shr 1;
res:=0;
if (l<=m) then res:=res+query(l,r,nowl,m,root*2);
if (m+1<=r) then res:=res+query(l,r,m+1,nowr,root*2+1);
exit(res);
end;
begin
readln(n,m);
fillchar(lazy,sizeof(lazy),0);
build(1,n,1);
readln;
while (m>0) do
begin
read(c);
if c='Q' then
begin
readln(i,j);
writeln(query(i,j,1,n,1));
end
else
begin
readln(i,j,k);
update(i,j,1,n,1,k);
end;
dec(m);
end;
end.
