线段树区间修改区间查询模板

  • 内容
  • 评论
  • 相关

一年半以前的古老代码了,现在拿出来可能以后用得上,方便找。

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.

不要在意我的过程名字啦~

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据