JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor sparse table algorithm
 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...
 Re: sparse table algorithm (response to post by quanchi) | Reply You can preprocess log[i] for i from 0 to N in O(N).
 Re: sparse table algorithm (response to post by Cosmin.ro) | Reply oh ok thanks
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor sparse table algorithm Previous Thread  |  Next Thread