胜者树是一种数据结构，特点如下：

1. 它是一棵完全二叉树。也就是说，除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。
2. 这棵树的所有叶子结点是原始数据（见下文样例）。
3. 对于所有非叶子结点，取两个儿子中更优秀的值，就是父亲结点的值，故名胜者树。
4. 由于胜者树是完全二叉树，因此如果把根结点编号为1，第二层的结点分别是2、3，第三层是4、5、6、7……那么我们就能发现：每一个非叶子结点的左儿子编号都是它的编号乘以2，右儿子编号是它的编号乘以2加上1。

好吧，如果你像我一样不喜欢看大堆的文字，那就撇开理论知识，我们先来看一个例子。

如上图，我们有原始数列a={4,2,9,1}，两两比对，优秀者成为更高层的结点。可知根结点的值就是原始数据中最优秀的值。容易推算，建树的时间复杂度仅为O(n)。程序如下：

void build_tree ( int _left , int _right , int _node ) {	if ( _left == _right ) tree[_node].value = a[_left] ;		else {			int _middle = ( _left + _right ) >> 1 ;			int l_child = _node << 1 ;			int r_child = l_child + 1 ;						build_tree ( _left , _middle , l_child ) ;			build_tree ( _middle+1 , _right , r_child ) ;			tree[_node] = _cmp ( tree[l_child] , tree[r_child] ) ? tree[l_child] : tree[r_child] ;		}	return ;} //初始建树调用build_tree(1,n,1)

但是！还有但是！如果只是这样的话，那效率和直接全部找一遍不是一样？优势何在？？

胜者树可以帮助我们快速找到数据中根据某一个规则决定的最优者，而且还可以

快速修改。为什么这么说呢？我们再来看一个例子。

如上图，当我们把2修改为5时，其相应的父结点也要重新判断并更新一遍。而其它没有受到影响的结点则并不会被访问。从根结点开始，判断要被修改的是左子树还是右子树，不断向下，直到最后一层。修改完之后回溯，顺便维护。

时间复杂度相当于二分，只需O(logN)。程序如下：

 

void

_insert

(

int

_left

,

int

_right

,

int

_k

,

int

new_value

,

int

_node

)

{

if ( _left == _right )		tree[_node].value = a[_left] ;	else {		int _middle = (_left+_right) >> 1 ;		int l_child = _node << 1 ;		int r_child = l_child + 1 ;				if ( _k <= _middle )			_insert ( _left , _middle , _k , new_value , l_child ) ;		else			_insert ( _middle+1 , _right , _k , new_value , r_child ) ;				tree[_node] = _cmp ( tree[l_child] , tree[r_child] ) ? tree[l_child] : tree[r_child] ;	}	return ;} //初始调用_insert(1,n,k,value,1)

 by LKB