董卓大家想必都听过吧。
(建议大家看看这个视频 以更好地了解董卓)
大家看完都知道了,董卓那边的人都喜欢用拳头说话
但,要是那边打起架来了,怎么记录谁打赢谁呢?
这就是我们今天要讲的——胜者树!
(往期分享点赞和阅读量都非常惨淡,希望各位可以点个赞或者帮忙宣传一下)
一,建树
先来看看胜者树的建树方法:
利用类似于树状数组的形式,运用二分,如果两端在同一个位置,则不需要打擂台,直接讲数据输入,并记录下标,如果不同,则建立左子树和右子树,随后将左子树和右子树的最强节点打擂台记录。
//a为原始数组,c储存原始数组下标,s储存胜者下标
void build(int l,int r,int rt)//l为左端点,r为右端点,rt为当前节点下标
{
if(l==r)//如果两端重叠
{
cin>>a[l];//就剩一个不用打(总不能自己打自己)
s[rt]=l;
c[l]=rt;
//记录
return ;
}
int mid=(l+r)/2;
build(l,mid,rt*2);
build(mid+1,r,rt*2+1);
//建左右子树
s[rt]=a[s[rt*2]]<a[s[rt*2+1]]?s[rt*2]:s[rt*2+1];//这里可以自行更改,本例使用的是求最小值,下面也一样
}
二,求a数组中的最小值
不断除以2,直到根节点,途中不断求最优解,即可得到最小值
void adjust(int rt)
{
while(rt>1)
{
rt=rt/2;
s[rt]=a[s[rt*2]]<a[s[rt*2+1]]?s[rt*2]:s[rt*2+1];//这里与建树函数的最后一句相同
}
}
三,求a数组一段的最小值
与建树差不多的思路,也是不断分两段
void query(int l,int r,int ll,int rr,int rt)//ll和rr为我们要求的区间
{
if(ll<=l && rr>=r) return s[rt];//区间包含则直接输出
int mid=(l+r)/2
int p1=0,p2=0;
if(ll<=mid) p1=query(l,mid,ll,rr,rt*2);//左子树
if(rr>mid) p2=query(mid+1,r,ll,rr,rt*2+1);//右子树
return a[p1]<a[p2]?p1:p2;//打擂台
}
...
cout<<a[query(原数组起始坐标,原数组末尾坐标,区间左端编号,区间右端编号,根节点位置)];
胜者树,就这么简单