每个节点维护的是区间的最小值#include cstdio #include iostream #include vector #include cmath #include queue #include algorithm #include cstring typedef long long ll; const int INF 1e6; const int maxn 1e5; using namespace std; int N, dat[2 * maxn]; //初始化 void Init(int n){ //将N扩大为2的倍数方便使用 N 1; while(N n)N * 2; for(int i 0; i N * 2 - 1; i) dat[i] INF; } //更新 void Updt(int k, int a){ //叶子结点 k N - 1; dat[k] a; //回溯 while(k 0){ k (k - 1) / 2; dat[k] min(dat[k * 2 1], dat[k * 2 2]); } } //查询 int Query(int a, int b, int k, int l, int r){ //不相交 if(r a || b l) return INF; //真属于 else if(l a b r) return dat[k]; else{ int vl Query(a, b, k * 2 1, l, (l r) / 2); int vr Query(a, b, k * 2 2, (l r) / 2, r); return min(vl, vr); } } //测试函数 int main(){ freopen(D:\\钢铁程序员\\程序数据\\081RMQ.txt, r, stdin); scanf(%d, N); Init(N); for(int i 0; i N; i){ int a; scanf(%d, a); Updt(i, a); } cout Query(0, 7, 0, 0, N) endl; return 0; }
)
