JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor sparse table algorithm Revision History (5 edits)
sparse table algorithm
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...
sparse table algorithm
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 the references which say O(1) so most probably i am wrong.
but still i doubt it...
sparse table algorithm
after preprocessing for the query (M[i][j]) we take two overlapping interval (i,k) and (j-2^k+1,k) (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 the references which say O(1) so most probably i am wrong.
but still i doubt it...
sparse table algorithm
after preprocessing for the query (M[i][j]) we take two non overlapping interval (i,k) and (j-2^k+1,k) (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 the references which say O(1) so most probably i am wrong.
but still i doubt it...
sparse table algorithm
after preprocessing for the query (M[i][j]) we take two non overlapping interval (i,k) and (j-2^k+1,k) (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 the references which say O(1) so most probably i am wrong.
but still i doubt abt it
sparse table algorithm
after preprocessing for the query (M[i][j]) we use k
which is equal to [log(j-i+1)].

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 the references which say O(1) so most probably i am wrong.
but still i doubt abt it