Skip to content

Instantly share code, notes, and snippets.

@tanvir002700

tanvir002700/compute sparse table.cpp

Created September 21, 2015 15:09
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/78a3e0b878e21e9590db to your computer and use it in GitHub Desktop.
Save tanvir002700/78a3e0b878e21e9590db to your computer and use it in GitHub Desktop.
Download ZIP
Sparse Table
Raw
compute sparse table.cpp
void Compute_ST(int N)
{
for (int i=0;i<N;i++)ST[0][i] = i;
for (int k = 1;(1 << k)<N; k++)
{
for (int i=0;i+(1<<k)<=N;i++)
{
int x = ST[k-1][i];
int y = ST[k-1][i+(1<<k-1)];
ST[k][i]=A[x]<=A[y]?x:y;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment