线段树，维护区间修改的利器，种类繁多。以其码量巨大的特点骇人听闻。
\(OIerhhx\)为了让线段树的使用方便更加方便简洁，不再苦恼，于是写下了这篇博客。
这一部分主要是为了梳理线段树代码：减化码量，矫正易错。
/*important*/
线段树结构体
{
懒标记+其他信息
}
lson函数（用于遍历函数查询子区间）//简化码量
{
return (l+r)/2;
}
rson函数（用于遍历函数查询子区间）//简化码量
{
return (l+r)/2+1;
}
maketag函数(用于遍历函数修改tag)//简化码量
{
/*仅对于该修改对该节点的懒标计和其他信息*/
}
pushdown函数(用于遍历函数更新)//简化码量
{
/*用该节点tag修改子节点信息+清空tag*/
}
update函数(用于子节点回溯后更新父节点)//简化码量
{
子节点比较求值
}
建树函数
{
子区间：预处理+return
其他区间：预处理+update
}
遍历函数
{
在修改/查询区间内：修改信息（/*仅对于该修改对该节点的懒标计和其他信息*/）/统计信息+return
pushdown
与左子区间交集
递归
与右子区间交集
update
return
}
以P3372 【模板】线段树 1为例：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+100;
int n,m;
int a[N];
struct point{
int val,add,len;
}tree[N*8];
int lson(int l,int r)
{
return (l+r)/2;
}
int rson(int l,int r)
{
return (l+r)/2+1;
}
void update(int x)
{
tree[x].val=tree[x*2].val+tree[x*2+1].val;
return;
}
void pushdown(int x)
{
tree[x*2].val+=tree[x].add*tree[x*2].len;
tree[x*2+1].val+=tree[x].add*tree[x*2+1].len;
tree[x*2].add+=tree[x].add;
tree[x*2+1].add+=tree[x].add;
tree[x].add=0;
return;
}
void make(int x,int to)
{
tree[x].val+=to*tree[x].len;
tree[x].add+=to;
return;
}
void build(int l,int r,int x)
{
tree[x].len=r-l+1;
if(l==r)
{
tree[x].val=a[l];
return;
}
build(l,lson(l,r),x*2);
build(rson(l,r),r,x*2+1);
update(x);
return;
}
void ad(int l,int r,int x,int l1,int r1,int to)
{
if(l>=l1&&r<=r1)
{
make(x,to);
return;
}
pushdown(x);
if(lson(l,r)>=l1)
ad(l,lson(l,r),x*2,l1,r1,to);
if(rson(l,r)<=r1)
ad(rson(l,r),r,x*2+1,l1,r1,to);
update(x);
return;
}
int get(int l,int r,int x,int l1,int r1)
{
if(l>=l1&&r<=r1)
{
return tree[x].val;
}
pushdown(x);
int s=0;
if(lson(l,r)>=l1)
s+=get(l,lson(l,r),x*2,l1,r1);
if(rson(l,r)<=r1)
s+=get(rson(l,r),r,x*2+1,l1,r1);
update(x);
return s;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,n,1);
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int x,y,z;
cin>>x>>y>>z;
ad(1,n,1,x,y,z);
}
else
{
int x,y;
cin>>x>>y;
cout<<get(1,n,1,x,y)<<'\n';
}
}
return 0;
}
维护乘和加的线段树堪称所有线段树中最简单的一类，其关键在于线段树\(tag\)维护的顺序，我们采用先乘再加的形式。
原因在于用一个已经乘过的加\(tag\)，先加值，就没有办法再乘一次了。
以下是乘加线段树的模板：
P3373 【模板】线段树 2
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+100;
int n,m,p;
struct point{
int val,add,mul,len;
}tree[N*8];
int a[N];
inline int lson(int l,int r)
{
return (l+r)/2;
}
inline int rson(int l,int r)
{
return (l+r)/2+1;
}
inline void update(int x)
{
tree[x].val=(tree[x*2].val+tree[x*2+1].val)%p;
return;
}
inline void make1(int x,int to)
{
tree[x].add=(tree[x].add+to)%p;
tree[x].val=(tree[x].val+to*tree[x].len)%p;
return;
}
inline void make2(int x,int to)
{
tree[x].add=(tree[x].add*to)%p;
tree[x].mul=(tree[x].mul*to)%p;
tree[x].val=(tree[x].val*to)%p;
return;
}
inline void pushdown(int x)
{
tree[x*2].val=(tree[x].mul*tree[x*2].val+(tree[x*2].len*tree[x].add)%p)%p;
tree[x*2+1].val=(tree[x].mul*tree[x*2+1].val+(tree[x*2+1].len*tree[x].add)%p)%p;
tree[x*2].mul=(tree[x*2].mul*tree[x].mul)%p;
tree[x*2+1].mul=(tree[x*2+1].mul*tree[x].mul)%p;
tree[x*2].add=(tree[x*2].add*tree[x].mul+tree[x].add)%p;
tree[x*2+1].add=(tree[x*2+1].add*tree[x].mul+tree[x].add)%p;
tree[x].add=0;
tree[x].mul=1;
return;
}
inline void build(int l,int r,int x)
{
tree[x].len=r-l+1;
tree[x].mul=1;
if(l==r)
{
tree[x].val=a[l]%p;
return;
}
build(l,lson(l,r),x*2);
build(rson(l,r),r,x*2+1);
update(x);
return;
}
inline void ad(int l,int r,int x,int l1,int r1,int to)
{
if(l1<=l&&r1>=r)
{
make1(x,to);
return;
}
pushdown(x);
if(l1<=lson(l,r))
ad(l,lson(l,r),x*2,l1,r1,to);
if(r1>=rson(l,r))
ad(rson(l,r),r,x*2+1,l1,r1,to);
update(x);
return;
}
inline void mu(int l,int r,int x,int l1,int r1,int to)
{
if(l1<=l&&r1>=r)
{
make2(x,to);
return;
}
pushdown(x);
if(l1<=lson(l,r))
mu(l,lson(l,r),x*2,l1,r1,to);
if(r1>=rson(l,r))
mu(rson(l,r),r,x*2+1,l1,r1,to);
update(x);
return;
}
inline int get(int l,int r,int x,int l1,int r1)
{
if(l1<=l&&r1>=r)
{
return tree[x].val;
}
pushdown(x);
int sum=0;
if(l1<=lson(l,r))
sum=(sum+get(l,lson(l,r),x*2,l1,r1))%p;
if(r1>=rson(l,r))
sum=(sum+get(rson(l,r),r,x*2+1,l1,r1))%p;
update(x);
return sum;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>p;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int x,y,z;
cin>>x>>y>>z;
mu(1,n,1,x,y,z);
}
if(op==2)
{
int x,y,z;
cin>>x>>y>>z;
ad(1,n,1,x,y,z);
}
if(op==3)
{
int x,y;
cin>>x>>y;
cout<<get(1,n,1,x,y)<<'\n';
}
}
return 0;
}
最值线段树顾名思义，维护的是区间最值，更新方法于乘加线段树很类似，就不赘述了。
值得注意的是，加乘\(tag\)往往与赋值\(tag\)冲突，需要额外处理，例如将加乘操作只更新赋值\(tag\)，不更新加乘\(tag\)等。
以下是最值线段树的模板：
P1253 [yLOI2018] 扶苏的问题
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+100;
int n,q;
int a[N];
struct point{
int tag1,tag2,val;
}tree[N*8];
int lson(int l,int r)
{
return (l+r)/2;
}
int rson(int l,int r)
{
return (l+r)/2+1;
}
void update(int x)
{
tree[x].val=max(tree[x*2].val,tree[x*2+1].val);
return;
}
void maketag1(int x,int to)
{
tree[x].tag1=to;
tree[x].tag2=0;
tree[x].val=to;
return;
}
void maketag2(int x,int to)
{
if(tree[x].tag1==LLONG_MIN)
tree[x].tag2+=to;
else
tree[x].tag1+=to;
tree[x].val+=to;
return;
}
void pushdown(int x)
{
if(tree[x].tag1!=LLONG_MIN)
{
maketag1(x*2,tree[x].tag1);
maketag1(x*2+1,tree[x].tag1);
}
maketag2(x*2,tree[x].tag2);
maketag2(x*2+1,tree[x].tag2);
tree[x].tag1=LLONG_MIN;
tree[x].tag2=0;
return;
}
void build(int l,int r,int x)
{
tree[x].tag1=LLONG_MIN;
if(l==r)
{
tree[x].val=a[l];
return;
}
build(l,lson(l,r),x*2);
build(rson(l,r),r,x*2+1);
update(x);
return;
}
void change1(int l,int r,int x,int l1,int r1,int to)
{
if(l>=l1&&r<=r1)
{
maketag1(x,to);
return;
}
pushdown(x);
if(lson(l,r)>=l1)
change1(l,lson(l,r),x*2,l1,r1,to);
if(rson(l,r)<=r1)
change1(rson(l,r),r,x*2+1,l1,r1,to);
update(x);
return;
}
void change2(int l,int r,int x,int l1,int r1,int to)
{
if(l>=l1&&r<=r1)
{
maketag2(x,to);
return;
}
pushdown(x);
if(lson(l,r)>=l1)
change2(l,lson(l,r),x*2,l1,r1,to);
if(rson(l,r)<=r1)
change2(rson(l,r),r,x*2+1,l1,r1,to);
update(x);
return;
}
int get(int l,int r,int x,int l1,int r1)
{
if(l>=l1&&r<=r1)
{
return tree[x].val;
}
int sum=LLONG_MIN;
pushdown(x);
if(lson(l,r)>=l1)
sum=max(sum,get(l,lson(l,r),x*2,l1,r1));
if(rson(l,r)<=r1)
sum=max(sum,get(rson(l,r),r,x*2+1,l1,r1));
update(x);
return sum;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
while(q--)
{
int op;
cin>>op;
if(op==1)
{
int l,r,x;
cin>>l>>r>>x;
change1(1,n,1,l,r,x);
}
if(op==2)
{
int l,r,x;
cin>>l>>r>>x;
change2(1,n,1,l,r,x);
}
if(op==3)
{
int l,r;
cin>>l>>r;
cout<<get(1,n,1,l,r)<<'\n';
}
}
return 0;
}
区间前后缀线段树，较前两种少见很多。他更为灵活，并且可以解决很多抽象的问题，例如：最大字段和，最长相间\(01\)串等等，也算是出正解、考场得分的利器。但同样的，他的难度也相较更大。
我们选择其中较为灵活的一种来讲解：最长相间\(01\)串。其余的均可以通过他类比。
以下是最长相间\(01\)串的模板：
P6492 [COCI2010-2011#6] STEP
区间前后缀线段树，所维护的不再是简单的\(tag\)而是多变的更新操作。
我们人为的将区间分成了子段，因此除了单个子区间的贡献\((1)\)，还要考虑子区间因更新操作所带来的合并与分裂的贡献\((2)\)。
我们分别讨论这两种贡献：
\((1)\):
在这种情况中，不涉及区间的合并与分裂操作。
我们只简单讨论整个子段的贡献，与普通线段树无异。
因此我们维护区间总贡献即可。
\((2)\)
我们考虑简化操作。
对于维护时，我们人为将所有区间拆开，这样我们就只用考虑合并的贡献，而不用考虑分裂的贡献了。
对于合并，我们延断点向两边扩展，根据贪心的思想，我们希望两边延伸出的部分，贡献都尽量大，即左区间后缀和右区间前缀的贡献尽量大。因此我们维护区间前缀和后缀的最值即可解决情况\((2)\)的问题。
问题来了，怎么维护前缀和后缀呢？
我们考虑一个区间在大多数情况下的最大前缀都是左子区间的最大前缀，但不排除有特殊情况：这个区间的前缀比左子区间本身更大，显然，我们特判一下，加上右子区间的最大前缀即可。后缀同理。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n,q;
int a[N];
struct point{
int lsum,rsum,len,sum;
}tree[N*8];
int lson(int l,int r)
{
return (l+r)/2;
}
int rson(int l,int r)
{
return (l+r)/2+1;
}
void build(int l,int r,int x)
{
tree[x].len=r-l+1;
tree[x].lsum=1;
tree[x].rsum=1;
tree[x].sum=1;
if(l==r)
return;
build(l,lson(l,r),x*2);
build(rson(l,r),r,x*2+1);
return;
}
void update(int x,int l,int r)
{
tree[x].sum=max(tree[x*2].sum,tree[x*2+1].sum);
tree[x].lsum=tree[x*2].lsum;
tree[x].rsum=tree[x*2+1].rsum;
if(a[lson(l,r)]!=a[rson(l,r)])
{
tree[x].sum=max(tree[x].sum,tree[x*2].rsum+tree[x*2+1].lsum);
if(tree[x].lsum==tree[x*2].len)
tree[x].lsum+=tree[x*2+1].lsum;
if(tree[x].rsum==tree[x*2+1].len)
tree[x].rsum+=tree[x*2].rsum;
}
return;
}
void change(int l,int r,int x,int to)
{
if(l==r)
{
a[to]^=1;
return;
}
if(lson(l,r)>=to)
change(l,lson(l,r),x*2,to);
if(rson(l,r)<=to)
change(rson(l,r),r,x*2+1,to);
update(x,l,r);
return;
}
int query()
{
return tree[1].sum;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
build(1,n,1);
while(q--)
{
int x;
cin>>x;
change(1,n,1,x);
cout<<query()<<'\n';
}
return 0;
}
编辑:更改了标题。我对两个部分是否相同不太感兴趣，而是如果它们在一定的公差范围内彼此共线。如果是这样，那么这些线应该聚集在一起作为一个单独的线段。编辑:我想有一个简短的说法:我试图以一种有效的方式将相似的线段聚集在一起。假设我有线段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
4-01网络层向上提供的服务有哪两种？试比较其优缺点？虚电路服务和数据报服务。虚电路 优点： 1.可以提供可靠的通信服务 2.因为数据是沿着建立的虚电路进行传输的，因此分组的首部不需要携带完整的目的主机 的地址，只需要填写这条虚电路的编号（并不大的整数），因此减少了分组的开销。 3.所有分组可以按序到达，无重复、无丢失。 缺点： 1.每次通信需要建立连接（逻辑连接而非物理连接），数据传输启动慢。 2.同属于一条虚电路的分组只能按照同一路由进行转发，在这条通路上，只要有一个结点 出现故障，整条通路均无法工作。 3.因为网络层要保证可靠传输，所以使用虚电
以下是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