这是一种我自认为较快的解题方法，来献给大家，学习学习，讨论讨论。
（用用繁體字，很好看的！）（文章中“/”表示整除）
今天我剛好看了一下關於線段樹知識的書。
所謂線段樹，就是用一個一維數組來表示一棵二叉樹（類似堆排序吧？）。
例如：（用用C的）
int tree[100]; /*由于Pascal的習慣，我一般不用tree[0]的*/
于是就用tree[1]作為樹的根節點，然後他的左節點是tree[2],右節點是tree[3].
歸納來說，就是一個樹根節點為tree[k]，則左節點為tree[2*k]，右節點為tree[2*k+1].
這樣就構造出了一棵二叉樹！
然後就是把這個二叉樹的根節點tree[1]表示1至N之間的最大值，其左節點表示1至(N+1)/2之間的最大值，其右節點表示(N+2)/2之間的最大值。然後就一直按這種規律繼續下去。
假設x至y之間(x<=y)的最大值為get(1,N,1,x,y)表示1至N的這個節點序數為1，求x至y之間的最大值。
那麼一般方程式為get(L,R,k,x,y)=tree[k] 当(L=x)且(R=y)时
get(L,m,2*k,x,y) 当m>=y时
get(m+1,R,2*k+1,x,y) 当m<x时
max{get(L,m,2*k,x,m),get(m+1,R,2*k+1,m+1,y)} 否则的话，说明m在x与y之间
其中m=(x+y)/2，max(a,b)表示a與b之間的較大者。
這樣得到一個遞歸方程。
至於這麼用程序實現就看看你了^-^
如果有更好的解法，请告诉我，告诉大家，让我们一起进步！！
liouzhou_101
这是一种我自认为较快的解题方法，来献给大家，学习学习，讨论讨论。
（用用繁體字，很好看的！）（文章中“/”表示整除）
今天我剛好看了一下關於線段樹知識的書。
所謂線段樹，就是用一個一維數組來表示一棵二叉樹（類似堆排序吧？）。
例如：（用用C的）
int tree[100]; /*由于Pascal的習慣，我一般不用tree[0]的*/
于是就用tree[1]作為樹的根節點，然後他的左節點是tree[2],右節點是tree[3].
歸納來說，就是一個樹根節點為tree[k]，則左節點為tree[2*k]，右節點為tree[2*k+1].
這樣就構造出了一棵二叉樹！
然後就是把這個二叉樹的根節點tree[1]表示1至N之間的最大值，其左節點表示1至(N+1)/2之間的最大值，其右節點表示(N+2)/2之間的最大值。然後就一直按這種規律繼續下去。
假設x至y之間(x<=y)的最大值為get(1,N,1,x,y)表示1至N的這個節點序數為1，求x至y之間的最大值。
那麼一般方程式為get(L,R,k,x,y)=tree[k] 当(L=x)且(R=y)时
get(L,m,2*k,x,y) 当m>=y时
get(m+1,R,2*k+1,x,y) 当m max{get(L,m,2*k,x,m),get(m+1,R,2*k+1,m+1,y)} 否则的话，说明m在x与y之间
其中m=(x+y)/2，max(a,b)表示a與b之間的較大者。
這樣得到一個遞歸方程。
至於這麼用程序實現就看看你了^-^
如果有更好的解法，请告诉我，告诉大家，让我们一起进步！！
liouzhou_101
要更快的話 把優化輸入一起算在內 應該不錯= ]
http://blog.csdn.net/emailed/archive/2009/11/03/4761806.aspx
这是一种我自认为较快的解题方法，来献给大家，学习学习，讨论讨论。
（用用繁體字，很好看的！）（文章中“/”表示整除）
今天我剛好看了一下關於線段樹知識的書。
所謂線段樹，就是用一個一維數組來表示一棵二叉樹（類似堆排序吧？）。
例如：（用用C的）
int tree[100]; /*由于Pascal的習慣，我一般不用tree[0]的*/
于是就用tree[1]作為樹的根節點，然後他的左節點是tree[2],右節點是tree[3].
歸納來說，就是一個樹根節點為tree[k]，則左節點為tree[2*k]，右節點為tree[2*k+1].
這樣就構造出了一棵二叉樹！
然後就是把這個二叉樹的根節點tree[1]表示1至N之間的最大值，其左節點表示1至(N+1)/2之間的最大值，其右節點表示(N+2)/2之間的最大值。然後就一直按這種規律繼續下去。
假設x至y之間(x<=y)的最大值為get(1,N,1,x,y)表示1至N的這個節點序數為1，求x至y之間的最大值。
那麼一般方程式為get(L,R,k,x,y)=tree[k] 当(L=x)且(R=y)时
get(L,m,2*k,x,y) 当m>=y时
get(m+1,R,2*k+1,x,y) 当m max{get(L,m,2*k,x,m),get(m+1,R,2*k+1,m+1,y)} 否则的话，说明m在x与y之间
其中m=(x+y)/2，max(a,b)表示a與b之間的較大者。
這樣得到一個遞歸方程。
至於這麼用程序實現就看看你了^-^
如果有更好的解法，请告诉我，告诉大家，让我们一起进步！！
liouzhou_101
要更快的話 把優化輸入一起算在內 應該不錯= ]
http://blog.csdn.net/emailed/archive/2009/11/03/4761806.aspx
我的解法跟線段樹比較相近，不過可能我一次建全部的表，速度就慢了
基礎想法跟101的差不多
如果有8個數，3 1 2 9 7 4 5 5 ，取1到6
那直接比1到4的MAX和5到6的MAX
1到4的MAX
3 3 9
1 9
2
9
5到6的MAX
7 7
4
最後MAX為9
用tree的結構把每個node都串起來，前述數列整個表為
3 3 9 9
1 9 7
2 7
9 5
7
4
5
5