[理工] 演算法

[TokiyoHot (東京熱死胖子)]

各位大大好，第一次來這邊問問題，以後請多指教:>

Suppose that we are given a sequence of n unsorted values, say x1,x2,...,

xn, and at the same time, we are asked to qucikly answer repeated queries

defined as follows: Given i and j, where 1<=i<j<=n, find the smallest value

in xi, xi+1,....,xj.


(a) Please design a data structure that uses O(n^2) space and answers the

queries in O(1) time.


(b) Please design a data structure that uses O(n) space and answers the queries

in O(logn) time.

以上，求解，感恩

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.123.237.64
※ 編輯: TokiyoHot       來自: 140.123.237.64       (11/13 23:11)
推 ddczx:a.建A=n*n矩陣,A(i,j)=smallest value in xi, xi+1,....,xj
→ ddczx:b.建BST,找最小in xi, xi+1,....,xj則坐中序追蹤,直到找到xt
→ ddczx:存在滿足i<=t<=j
推 FRAXIS:這是哪裡的考題阿？
→ FRAXIS:中序追蹤不一定可以在O(lg n)的時間內做完..
→ TokiyoHot:喔~抱歉這幾天比較忙.. 這是交大生資的考題
→ TokiyoHot:ddczx大大我看不太懂您的解法...