289
技術社區[雲棲]
線段樹和RMQ解析和模板
這幾天在看RMQ的題目，但是很多RMQ的題目也可以用線段樹解決。。。
看來兩者之間有很多關係，那就都好好看吧。。。下麵先貼出一個大牛對兩者的解釋。。
RMQ (Range Minimum/Maximum Query)問題是指：
對於長度為n的數列A，回答若幹詢問RMQ(A,i,j)(i,j<=n)，返回數列A中下標在[i,j]裏的最小(大）值，也就是說，RMQ問題是指求區間最值的問題
主要方法及複雜度(處理複雜度和查詢複雜度)如下:
1.樸素（即搜索） O(n)-O(n)
2.線段樹(segment tree) O(n)-O(qlogn)
3.ST（實質是動態規劃） O(nlogn)-O(1)
線段樹方法:
線段樹能在對數時間內在數組區間上進行更新與查詢。
定義線段樹在區間[i, j] 上如下：
第一個節點維護著區間 [i, j] 的信息。
if i<j , 那麼左孩子維護著區間[i, (i+j)/2] 的信息，右孩子維護著區間[(i+j)/2+1, j] 的信息。
可知 N 個元素的線段樹的高度 為 [logN] + 1(隻有根節點的樹高度為0) .
下麵是區間 [0, 9] 的一個線段樹:
線段樹和堆有一樣的結構, 因此如果一個節點編號為 x ，那麼左孩子編號為2*x 右孩子編號為2*x+1.
使用線段樹解決RMQ問題，關鍵維護一個數組M[num]，num=2^(線段樹高度+1).
M[i]:維護著被分配給該節點(編號:i 線段樹根節點編號:1)的區間的最小值元素的下標。
該數組初始狀態為-1.
線段樹的CPP代碼：
#include<iostream>
using namespace std;
#define MAXN 100
#define MAXIND 256 //線段樹節點個數
//構建線段樹,目的:得到M數組.
void initialize(int node, int b, int e, int M[], int A[])
{
if (b == e)
M[node] = b; //隻有一個元素,隻有一個下標
else
{
//遞歸實現左孩子和右孩子
initialize(2 * node, b, (b + e) / 2, M, A);
initialize(2 * node + 1, (b + e) / 2 + 1, e, M, A);
//search for the minimum value in the first and
//second half of the interval
if (A[M[2 * node]] <= A[M[2 * node + 1]])
M[node] = M[2 * node];
else
M[node] = M[2 * node + 1];
}
}
//找出區間 [i, j] 上的最小值的索引
int query(int node, int b, int e, int M[], int A[], int i, int j)
{
int p1, p2;
//查詢區間和要求的區間沒有交集
if (i > e || j < b)
return -1;
//if the current interval is included in
//the query interval return M[node]
if (b >= i && e <= j)
return M[node];
//compute the minimum position in the
//left and right part of the interval
p1 = query(2 * node, b, (b + e) / 2, M, A, i, j);
p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j);
//return the position where the overall
//minimum is
if (p1 == -1)
return M[node] = p2;
if (p2 == -1)
return M[node] = p1;
if (A[p1] <= A[p2])
return M[node] = p1;
return M[node] = p2;
}
int main()
{
int M[MAXIND]; //下標1起才有意義,保存下標編號節點對應區間最小值的下標.
memset(M,-1,sizeof(M));
int a[]={3,1,5,7,2,9,0,3,4,5};
initialize(1, 0, sizeof(a)/sizeof(a[0])-1, M, a);
cout<<query(1, 0, sizeof(a)/sizeof(a[0])-1, M, a, 0, 5)<<endl;
return 0;
}
ST算法（Sparse Table）:它是一種動態規劃的方法。
以最小值為例。a為所尋找的數組.
用一個二維數組f(i,j)記錄區間[i,i+2^j-1](持續2^j個)區間中的最小值。其中f[i,0] = a[i];
所以，對於任意的一組(i,j)，f(i,j) = min{f(i,j-1),f(i+2^(j-1),j-1)}來使用動態規劃計算出來。
這個算法的高明之處不是在於這個動態規劃的建立，而是它的查詢：它的查詢效率是O(1).
假設我們要求區間[m,n]中a的最小值，找到一個數k使得2^k<n-m+1.
這樣，可以把這個區間分成兩個部分：[m,m+2^k-1]和[n-2^k+1,n].我們發現，這兩個區間是已經初始化好的.
前麵的區間是f(m,k)，後麵的區間是f(n-2^k+1,k).
這樣，隻要看這兩個區間的最小值，就可以知道整個區間的最小值！
RMQ CPP代碼
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define M 100010
#define MAXN 500
#define MAXM 500
int dp[M][18];
/*
*一維RMQ ST算法
*構造RMQ數組 makermq(int n,int b[]) O(nlog(n))的算法複雜度
*dp[i][j] 表示從i到i+2^j -1中最小的一個值(從i開始持續2^j個數)
*dp[i][j]=min{dp[i][j-1],dp[i+2^(j-1)][j-1]}
*查詢RMQ rmq(int s,int v)
*將s-v 分成兩個2^k的區間
*即 k=(int)log2(s-v+1)
*查詢結果應該為 min(dp[s][k],dp[v-2^k+1][k])
*/
void makermq(int n,int b[])
{
int i,j;
for(i=0;i<n;i++)
dp[i][0]=b[i];
for(j=1;(1<<j)<=n;j++)
for(i=0;i+(1<<j)-1<n;i++)
dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int rmq(int s,int v)
{
int k=(int)(log((v-s+1)*1.0)/log(2.0));
/* 或者int d = v - s+1 , k;
for(k = 0; (1<<k) <= d; k++) ;
k- -;*/
return min(dp[s][k],dp[v-(1<<k)+1][k]);
}
void makeRmqIndex(int n,int b[]) //返回最小值對應的下標
{
int i,j;
for(i=0;i<n;i++)
dp[i][0]=i;
for(j=1;(1<<j)<=n;j++)
for(i=0;i+(1<<j)-1<n;i++)
dp[i][j]=b[dp[i][j-1]] < b[dp[i+(1<<(j-1))][j-1]]? dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
}
int rmqIndex(int s,int v,int b[])
{
int k=(int)(log((v-s+1)*1.0)/log(2.0));
return b[dp[s][k]]<b[dp[v-(1<<k)+1][k]]? dp[s][k]:dp[v-(1<<k)+1][k];
}
int main()
{
int a[]={3,4,5,7,8,9,0,3,4,5};
//返回下標
makeRmqIndex(sizeof(a)/sizeof(a[0]),a);
cout<<rmqIndex(0,9,a)<<endl;
cout<<rmqIndex(4,9,a)<<endl;
//返回最小值
makermq(sizeof(a)/sizeof(a[0]),a);
cout<<rmq(0,9)<<endl;
cout<<rmq(4,9)<<endl;
return 0;
}
應用:http://acm.pku.edu.cn/JudgeOnline/problem?id=3264
Cpp代碼
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
#define maxn 50001
int a[maxn];
int dpmax[maxn][40];
int dpmin[maxn][40];
int getmin(int a,int b)
{
if(a<b) return a;
else return b;
}
int getmax(int a,int b)
{
if(a>b) return a;
else return b;
}
void Make_Big_RMQ(int n)
{
int i,j;
for(i=1;i<=n;i++) dpmax[i][0]=a[i];
for(j=1;j<=log((double)n)/log(2.0);j++)
for(i=1;i+(1<<j)-1<=n;i++)
{
dpmax[i][j]=getmax(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]);
}
}
void Make_Min_RMQ(int n)
{
int i,j;
for(i=1;i<=n;i++) dpmin[i][0]=a[i];
for(j=1;j<=log((double)n)/log(2.0);j++)
for(i=1;i+(1<<j)-1<=n;i++)
{
dpmin[i][j]=getmin(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]);
}
}
int get_big_rmq(int a,int b)
{
int k=(int)(log((double)(b-a+1))/log(2.0));
return getmax(dpmax[a][k],dpmax[b-(1<<k)+1][k]);
}
int get_min_rmq(int a,int b)
{
int k=(int)(log((double)(b-a+1))/log(2.0));
return getmin(dpmin[a][k],dpmin[b-(1<<k)+1][k]);
}
int main()
{
int n,i,q,x,y;
while(scanf("%d %d",&n,&q)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
Make_Big_RMQ(n);
Make_Min_RMQ(n);
for(i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
printf("%d\n",get_big_rmq(x,y)-get_min_rmq(x,y));
}
}
return 0;
}
最後更新：2017-04-03 05:39:35