程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3468(成段更新)

POJ 3468(成段更新)

編輯:C++入門知識

線段樹的成段更新
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. 


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved