线段树区间修改区间查询模板
一年半以前的古老代码了,现在拿出来可能以后用得上,方便找。
var s,y:array[1..1048576]of int64; n,m,i,k,a,b:longint; c:int64; procedure update(t:longint); begin s[t]:=s[t shl 1]+s[t shl 1 or 1]; end; procedure down(l,r,t:longint); var m:longint; begin if y[t]=0 then exit; m:=(l+r) shr 1; s[t shl 1]:=s[t shl 1]+(m-l+1)*y[t]; y[t shl 1]:=y[t shl 1]+y[t]; s[t shl 1 or 1]:=s[t shl 1 or 1]+(r-m)*y[t]; y[t shl 1 or 1]:=y[t shl 1 or 1]+y[t]; y[t]:=0; end; procedure build(l,r,t:longint); var m:longint; begin y[t]:=0; if (l=r) then read(s[t]) else begin m:=(l+r) shr 1; build(l,m,t shl 1); build(m+1,r,t shl 1 or 1); update(t); end; end; procedure change(l,r,t:longint); var m:longint; begin if (l>b) or (r<a) then exit; if (l>=a) and (r<=b) then begin s[t]:=s[t]+(r-l+1)*c; y[t]:=y[t]+c; exit; end; down(l,r,t); m:=(l+r) shr 1; change(l,m,t shl 1); change(m+1,r,t shl 1 or 1); update(t); end; function qq(l,r,t:longint):int64; var m:longint; sum:int64; begin if (l>b) or (r<a) then exit(0); down(l,r,t); if (l>=a) and (r<=b) then exit(s[t]); m:=(l+r) shr 1; sum:=qq(l,m,t shl 1)+qq(m+1,r,t shl 1 or 1); update(t); exit(sum); end; begin read(n); build(1,n,1); read(m); for i:=1 to m do begin read(k); if k=1 then begin read(a,b,c); change(1,n,1); end else begin read(a,b); writeln(qq(1,n,1)); end; end; end.
不要在意我的过程名字啦~
发表回复