实现功能——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 begin
10 if x<y then min:=x else min:=y;
11 end;
12 procedure built(z,x,y:longint);inline;
13 begin
14 if x=y then
15 read(a[z])
16 else
17 begin
18 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 begin
27 if l>r then exit(0);
28 if (x=l) and (r=y) then
29 begin
30 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 begin
40 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 begin
45 readln(n,m);
46 built(1,1,n);
47 readln;
48 for i:=1 to m do
49 begin
50 read(j);
51 case j of
52 1:begin
53 readln(a1,a2,a3);
54 op(1,1,n,a1,a2,a3);
55 end;
56 2:begin
57 readln(a1,a2);
58 writeln(cal(1,1,n,a1,a2,0));
59 end;
60 else halt;
61 end;
62 end;
63 end.
64