前置知识
二叉树
定义
基本操作复杂度： $ O(logn) $
线段树是一棵二叉树，每个节点表示序列上的一段区间，其中根节点表示区间[1,n]。
从根节点开始，只要区间长度不为1，就将区间划分为两半，并分给两个子节点。
若当前节点表示区间[l,r]，
当l≠r时，左孩子表示[l,(l+r)/2]，右孩子表示[(l+r)/2+1,r]；
当l=r时，该节点为叶子节点。
基本性质
性质1
线段树的总节点数为2n-1。
性质2
线段树的层数约为 $ log_{ 2 } n $ ，即每个叶节点到根节点的距离约为 \(log_{2}n\) 。
性质3
任何区间都可以用不超过 \(2log_{2}n\) 个节点组合而成。
编号
线段树的编号方式通常有两种：即2i和2i+1作i的孩子或按构建顺序编号。
存储
线段树的存储也有两种方式：多个数组或struct结构体。
以struct结构体数组为例:
（lc,rc分别为左右孩子的编号，sum为该区间的总和。
数组大小为序列长度两倍。
至于区间的左右端点[l,r]，可以存储，也可以递归时计算。
若需要节省空间，则不存储。）
构建
构建过程递归实现，
void build(int u,int l,int r)
（u为当前节点编号，l,r为区间端点）
从根节点开始构建，递归时计算并代入l,r，若l=r，该点为叶子节点，令sum=序列原值，否则，递归构建左右孩子，之后令sum=sum左孩子+sum右孩子。
在主程序中：
t=1;
build(1,1,n);
即可。
应用
单点修改
修改过程递归实现，
void update(int u,int l,int r,int x,int w)
（u当前节点编号,l和r为区间端点，x为要修改的位置，w为变化量）
从根节点开始修改，若当前点为叶子节点，使sum+=w并返回
否则判断x在左孩子还是右孩子，递归进行修改，之后令sum=左孩子sum+右孩子sum。
在主程序中调用：
update(1,1,n,x,y);
区间和查询
查询过程递归实现，
void query(int u,int l,int r,int ll,int rr)
（u为当前节点，l和r是区间端点，ll和rr分别为所查询区间的左右端点）
需要用外层定义变量ans储存答案。
从根节点开始，首先判断查询区间与节点区间是否完全重合，若重合，ans+=sum并返回，否则判断查询区间是否完全在左孩子或者右孩子，若是则递归查询。否则将查询区间拆分，两侧分别递归查询。
在主程序中：
ans=0;
query(1,1,n,x,y);
维护区间最大值/最小值
区间修改
我们在线段树的每个节点上再储存一个信息，称为“标记”，记为tag，表示该节点所包含的每个位置，都要再加上tag。
首先，像区间询问一样将区间对应到尽量少的节点上，
令它们
sum+=(r-l+1)*w;//增加的区间和
tag+=w;//增加标记
然后将sum信息向上pushup。
区间修改后的单点/区间查询
查询与之前类似，
查询过程递归实现，
void query(int u,int l,int r,int ll,int rr,int w)
但由于标记的出现，多了“下传标记”一步。
下传标记时，孩子的标记要叠加。
类似于pushup，标记下传的过程写入一个
void pushdown(int u,int l,int r)
注
一个节点上的tag一定已经计入自身的sum。
在修改和查询时，只要需要进入子节点，就一定要pushdown。
注意
当维护信息较多时，为简化代码，通常将类似于”a[u].sum=a[a[u].lc].sum+a[a[u].rc].sum”的上传信息的步骤写入void pushup(int u)并调用pushup(u);
并非原创，仅是整理，请见谅
编辑:更改了标题。我对两个部分是否相同不太感兴趣，而是如果它们在一定的公差范围内彼此共线。如果是这样，那么这些线应该聚集在一起作为一个单独的线段。编辑:我想有一个简短的说法:我试图以一种有效的方式将相似的线段聚集在一起。假设我有线段f(fx0,fy0)和(fx1,fy1)和g(gx0,gy0)和(gx1,gy1)这些来自计算机视觉算法边缘检测器之类的东西，在某些情况下，两条线基本相同，但由于像素容差而被视为两条不同的线。有几种情况f和g共享完全相同的端点，例如:f=(0,0),(10,10)g=(0,0),(10,10)f和g共享大致相同的端点和大致相同的长度，例如:f=(0,0.01
我想画一个点，大约1秒后我想画下一个点。这是否可能:我已经试过了:functionsimulate(i){setTimeout(function(){drawPoint(vis,i,i);},1000);}for(vari=1;i不幸的是，这是行不通的。它只是立即绘制整条线。 最佳答案 这是行不通的，因为for循环将立即运行到结束，setTimeouts将被同时调度，所有函数将同时触发。取而代之的是，这样做:vari=1;(functionloop(){if(i++>200)return;setTimeout(function(){
我正在尝试创建类似于UDK或MayaMaterial编辑器的东西http://www.google.com/search?q=udk+material+editor&oe=utf-8&rls=org.mozilla:en-US:official&client=firefox-a&um=1&ie=UTF-8&hl=en&tbm=isch&source=og&sa=N&tab=wi&biw=1144&bih=929通过单击一个连接并将其拖动到另一个连接，可以连接两个节点。WPF可以执行此操作，但我不知道如何以编程方式(使用C#，而不是XAML)绑定(bind)贝塞尔曲线的端点和控制点以跟随
我使用Fortune算法找到一组点的Voronoi图。我得到的是一个线段列表，但我需要知道哪些线段形成闭合多边形，并将它们放在一个由它们围绕的原始点散列的对象中。找到这些内容的最快方法是什么？？我应该从算法中保存一些重要信息吗？如果是什么？这是我在Java中从C++实现移植的fortune算法的实现hereclassVoronoi{//ThesetofpointsthatcontrolthecentersofthecellsprivateLinkedListpts;//Alistoflinesegmentsthatdefineswherethecellsaredividedprivat
见上图；基本上，我想要一个简单的测试来检查一个点是否在线段的范围内。我拥有的信息(或输入，如果您愿意)是点的坐标和线段终点的坐标。我想要的输出是一个简单的boolean值。我怎样才能以简单的方式检查它？ 最佳答案 使用内积可以简单统一的检查。两个vector之间的内积可以在几何上可视化为两个vector的长度乘以两者夹角的余弦的乘积，或者是其中一个vector的长度与(正交)投影长度的乘积另一个到由该vector确定的线上。在您的情况下，如果您将vectorv从线段的一个端点投影到所考虑的点，则该点位于允许区域内当且仅当投影落在段s
以下是http://www.spoj.pl/problems/LITE/的实现使用具有惰性传播的线段树。我是分割树的新手，我不明白为什么我会得到TLE。有人可以看看它并帮助我纠正我的错误吗？#include#include#include#include#defineMAX100000usingnamespacestd;intM[2*MAX+1];intflag[2*MAX+1];intcount;voidrefresh(intbegin,intend,intn){M[n]=end-begin+1-M[n];flag[n]=0;flag[n*2]=!flag[n*2];flag[n*2
是否可以有效地计算与数轴上的单个点P重叠的线段的数量？所有线段都位于一条数字线上(它是一个1-D世界，而不是一个3-D世界)。每条线段都有一个起始坐标X1和一个结束坐标X2。例子:LinesegmentAspansfromX1==1toX2==3LinesegmentBspansfromX1==2toX2==4LinesegmentCspansfromX1==3toX2==5LinesegmentDspansfromX1==1toX2==4----------------------------------------Ex1:LinesegmentsthatoverlappointP=
我正在从一个数据数组中实现线段树，我还想在更新一系列数据时保持树的最大/最小值。这是我遵循本教程的初步方法http://p--np.blogspot.com/2011/07/segment-tree.html.不幸的是它根本不起作用，逻辑对我来说很有意义，但我对b和e有点困惑，我想知道这是数据数组？或者它是树的实际范围？据我了解，max_segment_tree[1]应该包含[1,MAX_RANGE]范围内的max而min_segment_tree[1]应该包含范围[1,MAX_RANGE]的min。intdata[MAX_RANGE];intmax_segment_tree[3*MA
我正在处理计算机图形学。我想表示一条有两个端点的线，然后我想要我的Line2d类有一个返回Vector2d的方法对象。假设，我有以下类(class):structPoint2d{intx;inty;};然后，我可以很容易地用两点表示一条线段:classLineSegment2d{private:Point2dstart;Point2dend;public:......};根据定义，vector由大小和方向组成。classVector2d{private:Point2dp;public:doubleMagnitude(void);PointComponent(void);Vector2d
我有一条射线，我需要找到它命中的最近线段。我认为如果我先对线段进行排序，可以在O(logn)时间内完成此操作，但我不记得如何对它们进行排序......我认为某种树最有效，但我该如何排序他们的起点和终点？如果可能的话，我还想快速插入到这个数据结构中。一条射线与一条线段有很多代码，但我需要一些关于一条射线与多条线段的代码...我不知道要用谷歌搜索什么术语。适当文章的链接很好，C++代码更好。谢谢!:)PS:线段实际上是非自相交多边形的边，按CCW顺序排序...但我认为以不同的方式排序它们可能有一些优势？这都是二维的。再三考虑，我不完全确定这是否可能。某种空间划分可能会有所帮助，但除此之