Skip to content

Instantly share code, notes, and snippets.

@tanvir002700

tanvir002700/sparse table query.cpp

Created September 21, 2015 15:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tanvir002700/076bd41527c55d03d3e4 to your computer and use it in GitHub Desktop.
Save tanvir002700/076bd41527c55d03d3e4 to your computer and use it in GitHub Desktop.
Download ZIP
Sparse Table
Raw
sparse table query.cpp
int RMQ(int i, int j)
{
int k = log2(j-i);
int x = ST[k][i];
int y = ST[k][j-(1<<k)+1];
return A[x] <= A[y] ? x : y;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment