Spare Table
===
###### tags: `Algorithm`
Sparse Table 用來解決區間極值問題

## table
### query
* `q(a,b)`
* find level k
* `k=log(b-a+1)`
* `merge(sp[k][a],sp[k][b-(1<<k)+1])`
* `(1<<k)`: kthlevel length
* ex: `q(1,7)`
* level k = 2
* `merge(sp[2][1],sp[2][3])`
## code

const int N = 5e5, K = 30;
int st[K][N], n;

int build ()
{
    for (int i=0; i<n; i++)
        cin >> st[0][i];
    for (int j=1; (1<<j)<=n; j++)
        for (int i=0; i+(1<<j)<=n; i++)
            st[j][i] = max(st[j-1][i], st[j-1][i+(1<<(j-1))]);
}
int query (int l, int r)
{
    int j; for (j=0; (1<<(j+1))<=(r-l); j++);
    return max( st[j][l], st[j][r-(1<<j)]);
}