https://13331.org/26.html

http://en.wikipedia.org/wiki/Range_minimum_query

http://www.cnblogs.com/kuangbin/p/3227420.html

## BIT

樹狀數組解決 RMQ，由於 RMQ 問題無法區間相減，因此只能詢問前後綴以及單調的修改。

http://codeforces.com/gym/100460/problem/K

//}/* .................................................................................................................................. */ const int N = int(1e5) + 9; VII A, B; int a[N],b[N]; int n; namespace BIT{ int C1[N], C2[N]; void Add(int C[], int x, int d){ for (;x<=n;x+=low_bit(x)) checkMin(C[x], d); } int Sum(int C[], int x){ int res = INF; for (;x;x^=low_bit(x)) checkMin(res, C[x]); return res; } } using namespace BIT; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif FLC(C1, C2, 0x3f); int m; RD(n); REP(i, n) A.PB(MP(RD(), i)); REP(i, n) B.PB(MP(RD(), i)); SRT(A); SRT(B); A.PB(MP(INF, INF)); B.PB(MP(INF, INF)); DWN(i, n, 0){ Add(C1, n-i, A[i].se); Add(C2, n-i, B[i].se); } RD(m); REP(i, m) RD(a[i]); REP(i, m) RD(b[i]); // 1..n REP(i, m){ int aa = Sum(C1, n-UBD(A, MP(a[i], INF)) ); int bb = Sum(C2, n-UBD(B, MP(b[i], INF)) ); // // cout << aa << " " << bb << endl; if (aa == bb) puts("Draw"); else puts( aa < bb ? "Mike" : "Constantine"); } }

## Sparse Table

另一種區間分割方案，缺點是不能修改。

在 lca 問題和後綴數組求 lcp 問題中都經常使用。

int ST[LV][N]; int rmq(int l, int r){ if (l > r) swap(l, r); ++r; int lv = lg2(r-l); return min(ST[0][lv][l], ST[0][lv][r-(1<<lv)]); } for ( int lv = 1 ; (1 << lv) <= n ; lv ++ ){ for ( int i = 1 ; i + (1 << lv) <= n + 1 ; i ++ ){ ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + (1<<(lv-1))]); } }

HDU 2888 - Check Corners （矩形。。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1778847

REP(xx, lg2(n)+1) REP(yy, lg2(m)+1) if (xx+yy){ REP(x, n-_1(xx)+1) REP(y, m-_1(yy)+1){ if (xx){ ST[xx][yy][x][y] = max(ST[xx-1][yy][x][y], ST[xx-1][yy][x+_1(xx-1)][y]); } else{ ST[xx][yy][x][y] = max(ST[xx][yy-1][x][y], ST[xx][yy-1][x][y+_1(yy-1)]); } } }

POJ - 2019 Cornfields （正方形。。時空上降一個 log。。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1778846

ZOJ - 3614 Choir （維護方差。。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1778842

##### 線段樹

最大的好處是支持修改。

http://www.shuizilong.com/house/archives/spoj-3557-ioi04-hermes/