求一个zkw线段树模板（pascal）（单点修改，区间修改，求和，最值。。。）万分感谢。。

请问就要程序么？ 程序如下： var dep,tag,tree:array[1..1000000]of longint//dep:节点深度tag:修改标签 h,n:longint//tree:节点值 procedure refresh(what,data:longint)inline//更新节点的修改标签 begin tag[what]:=f1(tag[what],data)//f1(x,y)依据标签 y 更新标签 x 的函数 tree[what]:=f2(tag[what])//f2(x)将标签 x 转化为值的函数 endprocedure push_to_son(what:longint)inline//将节点标签传递至 2 儿子 begin if tag[what]=0 then exitif dep[what]<h then begin refresh(what shl 1,tag[what])refresh((what shl 1)or 1,tag[what])endtag[what]:=0endprocedure push_all_the_way(what:longint)inline//将某叶节点的所有祖先至上而下传递标签 var i:longintbegin for i:=dep[what]-1 downto 1 do push_to_son(what shr i)endprocedure group_change(l,r,towhat:longint)inline//整体修改 *** 作 var I,ll,rr:longint begin l:=(1 shl (h-1))+lr:=(1 shl (r-1))+rll:=lrr:=rpush_all_the_way(l)push_all_the_way(r)while l<r-1 do begin if l and 1=0 then refresh(l+1,towhat)if r and 1=1 then refresh(r -1,towhat)l:=l shl 1r:=r shl 1endfor i:=1 to h-1 do begin ll:=ll shr 1rr:=rr shr 1tree[ll]:=f3(tree[ll shl 1],tree[(ll shl 1)or 1])//f3:用于合并左右 2 儿子值的函数 tree[rr]:=f3(tree[rr shl 1],tree[(rr shl 1)or 1])endendprocedure point_change(what,towhat:longint)inline//单点修改 *** 作 var i:longintbegin what:=(1 shl (h-1))+whatpush_all_the_way(what)tree[what]:=towhatfor i:=1 to h-1 do begin what:=what shr 1 tree[what]:=f3(tree[what shl 1],tree[(what shl 1) or 1])endendfunction point_ask(what:longint):longintinline//点查询 *** 作 begin what:=(1 shl (h-1))+whatpush_all_the_way(what)exit(tree[what])endfunction group_ask(l,r:longint):longintinline//区间查询 *** 作 begin l:=(1 shl (h-1))+lr:=(1 shl (h-1))+rgroup_ask:=$define//$define:利于统计答案的预值 push_all_the_way(l)push_all_the_way(r)while l<r-1 do begin if l and 1=0 then group_ask:=f3(group_ask,tree[l+1])if r and 1=1 then group_ask:=f3(group_ask,tree[r -1])l:=l shr 1r:=r shr 1endendBEGIN Readln(n) Inc(n,2)//建立第 0 号不 n+1 号虚拟节点 H:=trunc(ln(n-1)/ln(2))+2//计算树高 1 log n Fillchar(tree,sizeof(tree),0)T g:=treedep:=treeFor x:=0 to h-1 do dep[1 shl x]:=x+1//计算每个节点所在位置的深度 For x:=1 to (1 shl h)-1 do if dep[x]=0 then dep[x]:=dep[x-1]//同上 END. 如果满意请给分~

累死了，给你写了个代码，可以一定要给我分啊

这种问题的要旨，在于节点上的stop值，将需要修改的地方暂且存在stop上，等到下一次修改的时候一起带下去（insert(......,k+stop))，

type tree=^node

node=record

l,r,stop,data:longint

left,right:tree

end

var i,j,t,n,s,t,k,m,l,r,ans:longint

root:tree

ch:char

procedure make(var s:treel,r:longint)

begin

new(s)s^.stop:=0s^.data:=0s^.l:=ls^.r:=r

s^.left:=nils^.right:=nil

if l<r then

begin

make(s^.left,l,(l+r) div 2)

make(s^.right,(l+r) div 2+1,r)

end

end

procedure insert(var s:treel,r,k:longint)

begin

if (l<=s^.l) and (s^.r<=r) then

begin

with s^ do

begin

inc(data,(r-l+1)*k)

inc(stop,k)

end

end

else

begin

if (s^.left^.l<=r) and (s^.left^.r>=l) then insert(s^.left,l,r,s^.stop+k)

if (s^.right^.l<=r) and (s^.right^.r>=l) then insert(s^.right,l,r,s^.stop+k)

s^.stop:=0

s^.data:=s^.left^.data+s^.right^.data

end

end

procedure ask(var s:treel,r:Longint)

begin

if (l<=s^.l) and (s^.r<=r) then

begin

inc(ans,s^.data)

end

else

begin

if (s^.left^.l<=r) and (s^.left^.r>=l) then ask(s^.left,l,r)

if (s^.right^.l<=r) and (s^.right^.r>=l) then ask(s^.right,l,r)

end

end

begin

readln(n,m)

make(root,1,n)

for i:=1 to n do

begin

read(t)

insert(root,i,i,t)

end

for i:=1 to m do

begin

read(ch)

if ch='A' then //ask

begin

readln(l,r)

ans:=0

insert(root,l,r,0)

ask(root,l,r)

writeln(ans)

end

else if ch='C' then //change

begin

readln(s,t,k)

insert(root,s,t,k)

end

end

end.

一般是10^8左右，但是还要看常数，比如说for循环1亿次基本不会超。但是1亿次除法就很危险了。

LS说的比较全了。但是O(n^3)，500很危险，除非Floyd等常熟特别小的。O(nlogn)的话，线段树平衡树等都只能到10w，如果是动态树什么的只能四五万，堆的话可以20w左右，排序1000000个数基本上到顶了。

此外数组大小和寻址方式也会制约程序时间，比如。

for (int i=1i<=n++i)

for (int j=1j<=n++j) a[i][j]

和

for (int j=1j<=n++j)

for (int i=1i<=n++i) a[i][j]

差距很大

---