POJ 3468(成段更新）

线段树的成段更新
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.