RMQ（Range Minimum Query）
生活随笔
收集整理的這篇文章主要介紹了
RMQ（Range Minimum Query）
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>
問(wèn)題
????? RMQ問(wèn)題是求給定區(qū)間中的最值問(wèn)題。對(duì)于長(zhǎng)度為n的數(shù)列A，回答若干查詢RMQ(A, i, j)。返回?cái)?shù)組A中下標(biāo)在[i，j]里的最小值的下標(biāo)。比如數(shù)列 5,8,1,3,6,4,9,5,7 ? ? ?那么RMQ(2,4) = 3， RMQ(6,9) = 6.
解決方法
主要方法及復(fù)雜度(處理復(fù)雜度和查詢復(fù)雜度)如下:?
樸素（即搜索） O(n)-O(n)?
ST（實(shí)質(zhì)是動(dòng)態(tài)規(guī)劃） O(nlogn)-O(1)?
線段樹(shù)(segment tree) O(n)-O(qlogn)
樸素
????即是直接搜索，對(duì)被查詢的空間進(jìn)行直接遍歷，時(shí)間復(fù)雜度為O(n)
ST
??? Sparse Table,它是一種動(dòng)態(tài)規(guī)劃的方法。?
??? 以最小值為例。a為所尋找的數(shù)組.?用一個(gè)二維數(shù)組f(i,j)記錄區(qū)間[i,i+2^j-1](持續(xù)2^j個(gè))區(qū)間中的最小值。其中f[i,0] = a[i];?所以，對(duì)于任意的一組(i,j)，f(i,j) = min{f(i,j-1),f(i+2^(j-1),j-1)}來(lái)使用動(dòng)態(tài)規(guī)劃計(jì)算出來(lái)。?這個(gè)算法的高明之處不是在于這個(gè)動(dòng)態(tài)規(guī)劃的建立，而是它的查詢：它的查詢效率是O(1).?
???? 假設(shè)我們要求區(qū)間[m,n]中a的最小值，找到一個(gè)數(shù)k使得2^k<n-m+1.?這樣，可以把這個(gè)區(qū)間分成兩個(gè)部分：[m,m+2^k-1]和[n-2^k+1,n].我們發(fā)現(xiàn)，這兩個(gè)區(qū)間是已經(jīng)初始化好的.?
前面的區(qū)間是f(m,k)，后面的區(qū)間是f(n-2^k+1,k).?
???? 這樣，只要看這兩個(gè)區(qū)間的最小值，就可以知道整個(gè)區(qū)間的最小值！?
偽代碼：
//初始化INIT_RMQ//max[i][j]中存的是從i開(kāi)始的2^j個(gè)數(shù)據(jù)中的最大值，最小值類似，num中存有數(shù)組的值for?i?:?1?to?nmax[i][0]?=?num[i]for?j?:?1?to?log(n)/log(2)for?i?:?1?to?(n+1-2^i)max[i][j]?=?MAX（max[i][j-1],?max[i+2^(j-1)][j-1]）//查詢RMQ(i,?j)k?=?log(j-i+1)?/?log(2)return?MAX(max[i][k],?max[j-2^k+1][k])C++模板:
/***?@brief?sparse?algorithm*?@author?xiyan*?@date?2014/6/17*?@last?edit**/ #include?<cstdlib> #include?<iostream> #include?<cmath> typedef?unsigned?int?size_t; typedef?int?ssize_t; namespace?rmq{ using?namespace?std; template<typename?T> class?sparseTable{ public: ssize_t?createSt(const?T?*arrayPtr,?const?ssize_t?arraySize);????????? /*build?st?by?input*/ const?T?*searchSt(const?ssize_t?startPos,?const?ssize_t?endPos);????? /*lookup?the?min?val?from??startPos?to?endPos*/ virtual?~sparseTable(void);?????????????????????????????????????????????? /*destory?st?when?class?destory*/ virtual?void?debug(void); private:ssize_t?allocSt(const?ssize_t?arraySize);???????????????/*alloc?space?for?st*/ssize_t?initSt?(const?T?*arrayPtr);?????????????????????/*init?St*/ssize_t?stLog(ssize_t?size)?const;??????????????????????/*make?lg(size)*/???T?*?getItem(const?ssize_t?base,?const?ssize_t?logTots);?/*get?item?from?sparse?table*/????????????????????????void?destorySt(void);ssize_t?*getMaxLogTots(void){???????????????????????????return?&tot_row;}???????????????ssize_t?*getMaxBase(void){return?&tot_col;}T?*dpSt;???????????????????????????????????????????????????/*sparse?table*/ssize_t?tot_row;???????????????????????????????????????????/*sparee?table?tot?row*/ssize_t?tot_col;???????????????????????????????????????????/*sparse?table?tot?col?*/ }; /***?@brief?deinit?api?for?st*?@note?call?destorySt?to?do?clean?task*/ template<typename?T> void?sparseTable<T>::debug(void){cout?<<?"tot?nums(lg):"<<?*getMaxLogTots()?<<?endl;cout?<<?"tot?base????:"<<?*getMaxBase()?<<?endl;if(dpSt){for(ssize_t?tot?=?0;?tot?<?*getMaxLogTots();?tot++)for(ssize_t?base?=?0;?base?<?*getMaxBase();?base++){cout?<<?"Logtot?"?<<?tot;cout?<<?",";cout?<<?"base?"?<<?base;cout?<<?"|?->";cout?<<?*getItem(base,?tot)?<<?endl;}} } /***?@brief?deinit?api?for?st*?@note?call?destorySt?to?do?clean?task*/ template<typename?T> void?sparseTable<T>::destorySt(void){delete?dpSt; } /***?@brief?play?as?a?cleaner?when?destory?st**/ template<typename?T> sparseTable<T>::~sparseTable(void){destorySt(); } /***?@brief?2^n?<=?size,?return?n;?*?@return?n?success,?-1?fail**/ template<typename?T> ssize_t?sparseTable<T>::stLog(const?ssize_t?size)?const?{ssize_t?ans??=?0;if(size?<=?0){return?-1;}while(?(1?<<?ans)?<=?size){++ans;}ans--;return?ans; } /***?@brief?create?sparse?Table*?@param[in]?arrayPtr?base?data?store?in?array?for?building?sparse?table*?@param[in]?data?tots*?@return?0?success,?-1?fail*/ template<typename?T> ssize_t?sparseTable<T>::allocSt(const?ssize_t?arraySize){ssize_t?*maxBase????=?getMaxBase();ssize_t?*maxLogTots?=?getMaxLogTots();?*maxBase?????=?arraySize;*maxLogTots??=?stLog(arraySize);if(?*maxLogTots?<?0){return?-1;}*maxLogTots?+=?1;ssize_t?totSize?=?(*maxBase)?*?(*maxLogTots);dpSt?=?new?T[totSize];if(NULL?==?dpSt){return?-1;}return?0; }/***?@brief?get?Item?from?table?*?@note?*??????1.?row?act?as?totnums?cnt*??????2.?col?act?as?idx?for?base?num*??????3.?col?>=?row?for?Table?*/????? template<typename?T> T?*sparseTable<T>::getItem(const?ssize_t?base,?const?ssize_t?logTots){if(?!dpSt?||?base?<?0?||?logTots?<?0?||?base?>=?*getMaxBase()?||?logTots?>=?*getMaxLogTots()){return?NULL;}return?(&dpSt[logTots?*?(*getMaxBase())?+?base]); } /***?@brief?init?sparse?Table?by?input?*?@param[in]?arrayPtr?ptr?to?the?imput?array*/ template<typename?T> ssize_t?sparseTable<T>::initSt(const?T?*arrayPtr){for(ssize_t?base?=?0;?base?<?*getMaxBase();?base++){????????????T??*?itemPtr?=?getItem(base,?0);if(NULL?==?itemPtr){return?-1;}*itemPtr?=?arrayPtr[base];} #if?0cout?<<?"init?phase0?success"?<<?endl; #endiffor(ssize_t?logTots?=?1;?logTots?<?*getMaxLogTots();?logTots++){for(ssize_t?base?=?0;?((base?+?(1?<<??logTots)?)?<=?(*getMaxBase()));?base++){??T?*lItem?=?getItem(base,?logTots?-?1);?T?*rItem?=?getItem(base?+?(1?<<?(logTots?-?1)),?logTots?-?1);T?*cItem?=?getItem(base,?logTots);if(NULL?==?lItem?||?NULL?==?rItem||?NULL?==?cItem){return?-1;}*cItem?=?(*lItem?<?*rItem???*lItem?:?*rItem);}} #if?0cout?<<?"init?phase1?success"?<<?endl; #endifreturn?0; } /***?@brief?create?and?init?sparse?table*?@param[in]?arrayPtr?ptr?to?the?input?array*?@param[in]?arrSize??tot?nums?of?input**/ template<typename?T> ssize_t?sparseTable<T>::createSt(const?T?*arrayPtr,?const?ssize_t?arraySize){???????????? /*build?st?by?input*/if(allocSt(arraySize)??<?0){cout?<<?"alloc?sparse?table?fail"?<<?endl;return?-1;}if(initSt(arrayPtr)?<?0){destorySt();cout?<<?"init?sparse?table?fail"?<<?endl;return?-1;}return?0; }/***?@brief?search?the?min?num*?@param[in]?arrayPtr?ptr?to?the?input?array*?@param[in]?arrSize??tot?nums?of?input**/ template<typename?T> const?T?*?sparseTable<T>::searchSt(const?ssize_t?startPos,?ssize_t?endPos){???ssize_t?logPos;if(startPos?<?0?||?endPos?<?0||?startPos?>=?*getMaxBase()?||?endPos?>=?*getMaxBase()||?startPos?>?endPos){return?NULL;}logPos?=?stLog(endPos?-?startPos?+??1);if(logPos?<?0){return?NULL;}T?*lItem?=?getItem(startPos,?logPos);?T?*rItem?=?getItem(endPos?-?(1?<<?logPos)?+?1,?logPos);if(NULL?==?lItem?||?NULL?==?rItem){return?NULL;}return?(*lItem?<?*rItem???lItem?:?rItem); } }//?end?of?sparse?table?線段樹(shù)
線段樹(shù)能在對(duì)數(shù)時(shí)間內(nèi)在數(shù)組區(qū)間上進(jìn)行更新與查詢。?定義線段樹(shù)在區(qū)間[i, j] 上如下：?
第一個(gè)節(jié)點(diǎn)維護(hù)著區(qū)間 [i, j] 的信息。?
if i<j , 那么左孩子維護(hù)著區(qū)間[i, (i+j)/2] 的信息，右孩子維護(hù)著區(qū)間[(i+j)/2+1, j] 的信息。?
可知 N? 個(gè)元素的線段樹(shù)的高度 為 [logN] + 1(只有根節(jié)點(diǎn)的樹(shù)高度為0) .?
下面是區(qū)間 [0, 9]? 的一個(gè)線段樹(shù):?
?
線段樹(shù)和堆有一樣的結(jié)構(gòu), 因此如果一個(gè)節(jié)點(diǎn)編號(hào)為 x ，那么左孩子編號(hào)為2*x? ?右孩子編號(hào)為2*x+1.?
使用線段樹(shù)解決RMQ問(wèn)題，關(guān)鍵維護(hù)一個(gè)數(shù)組M[num]，num=2^(線段樹(shù)高度+1).?
M[i]:維護(hù)著被分配給該節(jié)點(diǎn)(編號(hào):i 線段樹(shù)根節(jié)點(diǎn)編號(hào):1)的區(qū)間的最小值元素的下標(biāo)。 該數(shù)組初始狀態(tài)為-1.?
?
參考文章
?
http://blog.csdn.net/huangxy10/article/details/7945856
http://blog.163.com/zhaohai_1988/blog/static/209510085201263011135062/
轉(zhuǎn)載于:https://my.oschina.net/u/572632/blog/280347
總結(jié)
以上是生活随笔為你收集整理的RMQ（Range Minimum Query）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： ASP.NET Hashtable输出J
- 下一篇： 重力感应机制和手机的屏幕绘画