线段树学习笔记
1. 原理
线段树是啥呢？
如图，就是一个数组的线段树。所以，线段树的前提是要有一个原数组。
假如，我想让你求数组中的区间和。那么肯定就有巨佬出现了：
呃……（空气安静3秒钟）
好吧，我们求区间最大值。这样，就能让这位巨佬哑口无言。
我们把数组分成多个段，就像上面的图，1-n 可以分为 1 - n/2 和 n/2+1 - n两个区域，然后又可以分为四个区域……所以呢，这是一个二叉树。只要我们最后分下去的区间已经分不下去了，只剩一个点了，那么就可以结束了。
如图，就是一个对于a数组的线段树。同一个颜色的是同一层。因为我们肯定没有2.5这种东西，所以我们需要取整，导致看起来不对称。
2. 建树
我们需要很多变量，我们慢慢来。
首先，我们先说明，每个节点的左儿子编号为2n，右儿子为2n+1。
以下，是我们需要的数组
int zhi[10001];//原数组
int fak[10001];//线段树数组
int qu_l[10001];//维护的区间 左范围
int qu_r[10001];//维护的区间 右范围
原数组的输入我就不讲了，如果你真的不知道，我建议你看这个：传送门
void in(int l,int r,int hao)//左范围，右范围，编号
{
if(l==r)
{
fak[hao]=zhi[l];
return ;
}
in(l,(l+r)/2,hao*2);
in((l+r)/2+1,r,hao*2+1);
fak[hao]=max(fak[hao*2],fak[hao*2+1]);
return ;
}
我们通过
in(1,n,1);
就可以让它建树啦！但是呢，我们还需要让它存下对应节点所维护的区间。所以，我们需要加上一些代码。
void in(int l,int r,int hao)//左，右，编号
{
if(l==r)
{
qu_l[hao]=l;
qu_r[hao]=r;//忘记记录害死猫
fak[hao]=zhi[l];
return ;
}
in(l,(l+r)/2,hao*2);
in((l+r)/2+1,r,hao*2+1);
fak[hao]=max(fak[hao*2],fak[hao*2+1]);
qu_l[hao]=l;
qu_r[hao]=r;//记录其维护的区间
return ;
}
3. 单点修改
如果我们要修改某些点的话，假如我们改第二个为5
只要包含这个点的，都需要修改。
void fix(int hao,int h,int zhi)//线段树所在编号 单点修改需要的编号 修改的值
{
if(qu_r[hao]==0 || qu_l[hao]==0)
{
return ;
}
if(qu_l[hao]==h && qu_r[hao]==h)
{
fak[hao]=zhi;
return ;
}
if(qu_l[hao]<=h && h<=qu_r[hao])
{
fix(hao*2,h,zhi);
fix(hao*2+1,h,zhi);
fak[hao]=max(fak[hao],zhi);
return ;
}
else
{
return ;
}
}
我们只需要
fix(1,[改变的位置],[改变的值]);
就完事了。
4. 区间查询
说了这么多，这个树依然没有体现出它巨大的作用。
那么，我们来输出区间最大值吧。我们继续用老图。
如果全包含，那么我们就分三种情况（我在这里被坑死了）
如果这个区间被左区间全包含，则走左边。
如果这个区间被右区间全包含，则走右边。
如果这个区间被两个区间都包含一些，那么切成两段求max。
int find(int l,int r,int hao)
{
if(l>r)
{
return 0;
}
if(qu_l[hao]<=l && r<=qu_r[hao])
{
if(qu_l[hao]==l && r==qu_r[hao])
{
return fak[hao];
}
else
{
if(qu_l[hao]==qu_r[hao])
{
return fak[hao];
}
else
{
if(qu_l[hao*2]<=l && r<=qu_r[hao*2])
{
return find(l,r,hao*2);
}
if(qu_l[hao*2+1]<=l && r<=qu_r[hao*2+1])
{
return find(l,r,hao*2+1);
}
return max(find(l,qu_r[hao*2],hao*2),find(qu_l[hao*2+1],r,hao*2+1));
}
}
}
else
{
return 0;
}
}
如果我们要求o到oo的最大值，那么
find(o,oo,1)
就是它的值。
5. 完成代码
输入格式：
先输入一个n，然后以后n个数输入原数组的值。
然后输入o，然后o行输入两个数oo，ooo，表示把oo位的数修改为ooo。
然后输入p，然后p行输入两个数pp，ppp，表示需要输出pp到ppp的最大值。
#include <cstdio>
int zhi[10001];//原数组
int fak[10001];//线段树数组
int fa[10001];//父亲节点 未使用 //
int left[10001];//左儿子编号 未使用 //
int qu_l[10001];//维护的区间 左范围
int right[10001]; //右儿子编号 未使用 //
int qu_r[10001];//维护的区间 右范围
int max(int o,int p)
{
if(o>=p)
{
return o;
}
else
{
return p;
}
}
void in(int l,int r,int hao)//左，右，编号
{
if(l==r)
{
qu_l[hao]=l;
qu_r[hao]=r;//忘记记录害死猫
fak[hao]=zhi[l];
return ;
}
in(l,(l+r)/2,hao*2);
in((l+r)/2+1,r,hao*2+1);
fak[hao]=max(fak[hao*2],fak[hao*2+1]);
qu_l[hao]=l;
qu_r[hao]=r;//记录其维护的区间
return ;
}
void fix(int hao,int h,int zhi)//线段树所在编号 单点修改需要的编号 修改的值
{
if(qu_r[hao]==0 || qu_l[hao]==0)
{
return ;
}
if(qu_l[hao]==h && qu_r[hao]==h)
{
fak[hao]=zhi;
return ;
}
if(qu_l[hao]<=h && h<=qu_r[hao])
{
fix(hao*2,h,zhi);
fix(hao*2+1,h,zhi);
fak[hao]=max(fak[hao],zhi);
return ;
}
else
{
return ;
}
}
int find(int l,int r,int hao)
{
if(l>r)
{
return 0;
}
if(qu_l[hao]<=l && r<=qu_r[hao])
{
if(qu_l[hao]==l && r==qu_r[hao])
{
return fak[hao];
}
else
{
if(qu_l[hao]==qu_r[hao])
{
return fak[hao];
}
else
{
if(qu_l[hao*2]<=l && r<=qu_r[hao*2])
{
return find(l,r,hao*2);
}
if(qu_l[hao*2+1]<=l && r<=qu_r[hao*2+1])
{
return find(l,r,hao*2+1);
}
return max(find(l,qu_r[hao*2],hao*2),find(qu_l[hao*2+1],r,hao*2+1));
}
}
}
else
{
return 0;
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&zhi[i]);
}
in(1,n,1);
int ooo;
scanf("%d",&ooo);
for(int i=1;i<=ooo;i++)
{
int o,oo;
scanf("%d %d",&o,&oo);
fix(1,o,oo);
}
scanf("%d",&ooo);
for(int i=1;i<=ooo;i++)
{
int o,oo;
scanf("%d %d",&o,&oo);
printf("%d\n",find(o,oo,1));
}
return 0;
}
6. 其他问题
如果想要区间修改等事项，请学习可持久化线段树。