JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
sparse table algorithm | Reply
after preprocessing for the query (M[i][j]) we take two overlapping intervals of length 2^k starting at i and j-2^k+1 (where k=[log(j-i+1)]) and compute the minimum value

the time taken to calculate k is O(logN)

but the query time given is O(1),shoudn't it be O(logN)?

i checked with some references which say O(1) so most probably i am wrong..
but still i doubt it...
Subject Author Date
sparse table algorithm quanchi Aug 24, 2007 at 2:53 PM EDT
Re: sparse table algorithm Cosmin.ro Aug 24, 2007 at 6:15 PM EDT
Re: sparse table algorithm quanchi Aug 25, 2007 at 1:25 AM EDT
RSS