算法模板——线段树6(二维线段树:区域加法+区域求和)(求助phile)

实现功能——对于一个N×M的方格,1:输入一个区域,将此区域全部值作加法;2:输入一个区域,求此区域全部值的和

其实和一维线段树同理,只是不知道为什么速度比想象的慢那么多,求解释。。。@acphile

(还有代码略恶心,求原谅。。。^_^)

 1 const tvp=8000000;
 2 var
 3    i,j,k,l,m,n,a1,a2,a3,a4,a5:longint;
 4    a,b:array[0..tvp] of longint;
 5    c1,c2:char;
 6 function max(x,y:longint):longint;inline;
 7          begin
 8               if x>y then max:=x else max:=y;
 9          end;
10 function min(x,y:longint):longint;inline;
11          begin
12               if x<y then min:=x else min:=y;
13          end;
14 function op(z,x1,y1,x2,y2,lx,ly,rx,ry,nu,d:longint):longint;inline;
15          var
16             a1,a2,a3,a4,a5:longint;
17          begin
18               if (lx>rx) or (ly>ry) then exit(0);
19               if (x1=lx) and (y1=ly) and (x2=rx) and (y2=ry) then
20                  begin
21                       b[z]:=b[z]+nu;
22                       exit(nu*(rx-lx+1)*(ry-ly+1));
23                  end;
24               a2:=op(z*4-2,x1,y1,(x1+x2) div 2,(y1+y2) div 2,lx,ly,min(rx,(x1+x2) div 2),min(ry,(y1+y2) div 2),nu,d);
25               a3:=op(z*4-1,x1,(y1+y2) div 2+1,(x1+x2) div 2,y2,lx,max(ly,(y1+y2) div 2+1),min(rx,(x1+x2) div 2),ry,nu,d);
26               a4:=op(z*4,(x1+x2) div 2+1,y1,x2,(y1+y2) div 2,max(lx,(x1+x2) div 2+1),ly,rx,min(ry,(y1+y2) div 2),nu,d);
27               a5:=op(z*4+1,(x1+x2) div 2+1,(y1+y2) div 2+1,x2,y2,max(lx,(x1+x2) div 2+1),max(ly,(y1+y2) div 2+1),rx,ry,nu,d);
28               a[z]:=a[z]+a2+a3+a4+a5;
29               exit(a2+a3+a4+a5);
30          end;
31 function cal(z,x1,y1,x2,y2,lx,ly,rx,ry,d:longint):longint;inline;
32          var a1,a2,a3,a4,a5:longint;
33          begin
34               if (lx>rx) or (ly>ry) then exit(0);
35               d:=d+b[z];
36               if (x1=lx) and (y1=ly) and (x2=rx) and (y2=ry) then exit(a[z]+d*(rx-lx+1)*(ry-ly+1));
37               a2:=cal(z*4-2,x1,y1,(x1+x2) div 2,(y1+y2) div 2,lx,ly,min(rx,(x1+x2) div 2),min(ry,(y1+y2) div 2),d);
38               a3:=cal(z*4-1,x1,(y1+y2) div 2+1,(x1+x2) div 2,y2,lx,max(ly,(y1+y2) div 2+1),min(rx,(x1+x2) div 2),ry,d);
39               a4:=cal(z*4,(x1+x2) div 2+1,y1,x2,(y1+y2) div 2,max(lx,(x1+x2) div 2+1),ly,rx,min(ry,(y1+y2) div 2),d);
40               a5:=cal(z*4+1,(x1+x2) div 2+1,(y1+y2) div 2+1,x2,y2,max(lx,(x1+x2) div 2+1),max(ly,(y1+y2) div 2+1),rx,ry,d);
41               exit(a2+a3+a4+a5);
42          end;
43 begin
44      readln(c1,n,m);
45      fillchar(a,sizeof(a),0);
46      fillchar(b,sizeof(b),0);
47      while not(eof) do
48            begin
49                 read(c1,a1,a2,a3,a4);
50                 case c1 of
51                      'L':begin
52                               readln(a5);
53                               op(1,1,1,n,m,a1,a2,a3,a4,a5,0);
54                      end;
55                      'k':begin
56                               readln;
57                               writeln(cal(1,1,1,n,m,a1,a2,a3,a4,0));
58                      end;
59                 end;
60            end;
61 end.       

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java 源码分析

动态规划

​ 动态规划一般来说和分治有点类似都是让他们去处理相同的子问题,但是在动态规划里面你会遇到更多的相同子问题。然后我们就会导致很多的重复计算,所以一般我们可...

3005
来自专栏xiaoxi666的专栏

最长滑道问题(非递归,C++)

题目描述请参考博客http://blog.csdn.net/sinat_30186009/article/details/52356053,在此表示感谢。

993
来自专栏每日一篇技术文章

OpenGL ES _ 着色器_纹理图像

玩过游戏的同学们,都知道在游戏人物身上穿的那个叫皮肤,专业点将那个就叫做纹理图像。GLSL 支持在顶点和片段着色器使用纹理图像。

1923
来自专栏帮你学MatLab

《Experiment with MATLAB》读书笔记(四)

读书笔记(四) 这是第四部分数组与矩阵 将代码复制到m文件即可运行 函数部分需新建m文件保存 %% 向量与矩阵 x = [2; 4] % ...

37211
来自专栏深度学习之tensorflow实战篇

tensorflow之tf.placeholder 与 tf.Variable区别对比

二者的主要区别在于 Variable:主要是用于训练变量之类的。比如我们经常使用的网络权重,偏置。 值得注意的是Variable在声明是必须赋予初始值。在训...

3294
来自专栏mwangblog

开始使用Octave

1914
来自专栏zingpLiu

机器学习之线性代数

  完整内容已上传到github:https://github.com/ZingP/machine-learning/tree/master/linear_al...

1711
来自专栏技术随笔

[RNN] Simple LSTM代码实现 & BPTT理论推导

4574
来自专栏漫漫深度学习路

tensorflow学习笔记(三十):tf.gradients 与 tf.stop_gradient() 与 高阶导数

gradient tensorflow中有一个计算梯度的函数tf.gradients(ys, xs),要注意的是,xs中的x必须要与ys相关,不相关的话,会报错...

1.4K9
来自专栏有趣的Python

7- 深度学习之神经网络核心原理与算法-模型的保存与加载

1545

扫码关注云+社区