找给定数组的任意长度子数组的最大值（Priority)
用赢者树的结构实现
也能过，就是慢点
详细见下：

/* 
    Title : RMQ(Range Minimum Query)问题的Binary Tree解法， 
            查询一指定数列任意一段区间内最(大)元素的位置 
    Time Complex : O(n) 预处理， O(logn) 每次查询 
    Space Complex : O(3*n) Total space 
    Author : song 
    Date : 9.3.2005 
*/ 
#include <cstdio> 
const int MAX = 1<<16;  //MAX is a power of 2 and just bigger than n 
int key[MAX];           //数列 
int n;                  //数列长度 
int pp[MAX*2];          //binary tree数组,pp[i]保存i子树覆盖的区间里最值的序号 

inline bool RMQcmp(int i, int j)    //比较函数 
{ 
    //like a heap, here we us > to get a Minimum Result, 
    //and < to get a Maximum one 
    return key[i] > key[j];      
}    

void RMQCreate()           //预处理，建树 
{ 
     int f = MAX, t = MAX + n - 1, i; 
     for(i = 0; i < n; ++i) 
        pp[i+MAX] = i; 
     for( ;f < t; f /= 2, t /= 2) 
     { 
        for(i = f; i < t ; i+= 2) 
        { 
            if( !RMQcmp(pp[i], pp[i+1]) ) 
                pp[i/2] = pp[i]; 
            else pp[i/2] = pp[i+1]; 
        } 
        if(!(t&1)) pp[t/2] = pp[t]; 
     } 
} 

int RMQFind(int ss, int ee)     //返回原数列key[ss - ee]之间最小元素的序号 
{ 
    int k, f, t; 
    ss += MAX, ee += MAX; 
    k = !RMQcmp(pp[ss] ,pp[ee]) ? pp[ss] : pp[ee]; 
    for( f = ss, t = ee; f < t; f/=2, t/=2) 
    { 
        if( !(f&1) && f + 1 < t && !RMQcmp(pp[f+1], k)) 
            k = pp[f+1]; 
        if( (t&1)  && t - 1 > f && !RMQcmp(pp[t-1], k)) 
            k = pp[t-1]; 
    } 
    return k; 
} 

int main() 
{ 
    /* 
        main()里做的事： 
        1.先初始化好key数列,及比较函数RMQcmp()。key[]的名字可改，只要cmp对应上就行。 
        2.调用RMQCreate()预处理 
        3.查询key[0,n-1]之间最小元素的序号，只需调用RMQFind(0, n-1) 
    */ 
    return 0; 
}    

• FT..这是线段树? (1898) yiyiyi4321 2006-04-19 18:27:30
  • 这个可以用线段树做的 (0) frkstyc 2006-04-19 18:37:49
    • 哦,谢了,不过他发的东西不是线段树吧 (0) yiyiyi4321 2006-04-19 19:50:39
      • 是RMQ->LCA (0) waterine 2006-11-10 15:16:23