首页 > 代码库 > 算法模板——线段树1（区间加法+区间求和）
算法模板——线段树1（区间加法+区间求和）
实现功能——1：区间加法；2：区间求和
最基础最经典的线段树模板。由于这里面操作无顺序之分，所以不需要向下pushup，直接累积即可
1 var 2 i,j,k,l,m,n,a1,a2,a3,a4:longint; 3 a,b:array[0..100000] of longint; 4 function max(x,y:longint):longint;inline; 5 begin 6 if x>y then max:=x else max:=y; 7 end; 8 function min(X,Y:LOngint):longint;inline; 9 begin10 if x<y then min:=x else min:=y;11 end;12 procedure built(z,x,y:longint);inline;13 begin14 if x=y then15 read(a[z])16 else17 begin18 built(z*2,x,(x+y) div 2);19 built(z*2+1,(x+y) div 2+1,y);20 a[z]:=a[z*2]+a[z*2+1];21 end;22 b[z]:=0;23 end;24 function op(z,x,y,l,r,d:longint):longint;inline;25 var a3,a4:longint;26 begin27 if l>r then exit(0);28 if (x=l) and (r=y) then29 begin30 b[z]:=b[z]+d;31 exit(d*(r-l+1));32 end;33 a3:=op(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),d);34 a4:=op(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,d);35 a[z]:=a[z]+a3+a4;36 exit(a3+a4);37 end;38 function cal(z,x,y,l,r,d:longint):longint;inline;39 begin40 if l>r then exit(0);d:=d+b[z];41 if (x=l) and (y=r) then exit(a[z]+d*(r-l+1));42 exit(cal(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),d)+cal(z*2+1,(x+y) div 2+1,y,max(l,(x+y) div 2+1),r,d));43 end;44 begin45 readln(n,m);46 built(1,1,n);47 readln;48 for i:=1 to m do49 begin50 read(j);51 case j of52 1:begin53 readln(a1,a2,a3);54 op(1,1,n,a1,a2,a3);55 end;56 2:begin57 readln(a1,a2);58 writeln(cal(1,1,n,a1,a2,0));59 end;60 else halt;61 end;62 end;63 end.64
算法模板——线段树1（区间加法+区间求和）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。