胜者树算法总结范文.doc

《胜者树算法总结范文.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、胜者树算法总结范文　　胜者树算法总结所谓胜者树，其实就是一棵完全二叉树，运用胜者树，我们可以求出固定的一段（或全部），经过每次修改后的最大值（或是最小值）。　　我们先要构建一棵满二叉树（如图）。　　根结点就是最大值（或是最小值）了。　　如何修改数列，更新这棵树？每一次更新，就重复就可以了。　　SlidingWindow#include#includeintk[1000100],t[4000100],p[4000100],y[1000100];intn,m,d,head;intmax(inta,intb){if(a>b)returna;el

2、sereturnb;}intmin(inta,intb){if(a>b)returnb;elsereturna;}voidbuild()//构建胜者树{for(inti=d;i<=d+m-1;i++){t[i]=k[i-d+1];p[i]=k[i-d+1];}//叶子结点for(inti=d+m;i<=d+d-1;i++){t[i]=-2000000000;p[i]=2000000000;}//补零for(inti=d-1;i>=1;i--){t[i]=max(t[i*2],t[i*2+1]);p[i]=min(p[i*2],p[i*2+

3、1]);}printf("%d",p[1]);y[1]=t[1];}voidupdata(intw,intvol)//更新胜者树{t[d+w-1]=vol;p[d+w-1]=vol;//更改叶子结点intr=(d+w-1)/2;while(r>=1){t[r]=max(t[r*2],t[r*2+1]);p[r]=min(p[r*2],p[r*2+1]);r/=2;}}intmain(){scanf("%d%d",&n,&m);d=1;while(dm)head-=m;//判断是否越界}printf("");for(inti=1;i<=

4、n-m+1;i++)printf("%d",y[i]);printf("");return0;}。　　　　内容仅供参考