一、題目大意

給出一個長度為 n（n<=50000)?數(shù)組 arr，進(jìn)行Q次查詢（Q<=200000），每次查詢的內(nèi)容為數(shù)組arr在 [L , R] 的切片的極差（最大元素 - 最小元素）

二、解題思路

1、線段樹

區(qū)間極差其實就是 區(qū)間內(nèi)最大值 - 區(qū)間內(nèi)最小，那么就想到RMQ，用線段樹去維護(hù)一個區(qū)間內(nèi)的最大和最小元素，然后根據(jù)問題的區(qū)間 L 和 R，找到相關(guān)的線段樹節(jié)點，從中找出 最大值最大的，然后減去最大值 最小的即可。

實現(xiàn)的方式就非常簡單了，因為是線段樹，所以就把葉子節(jié)點的數(shù)量擴展到滿足 2^i >= n_的最小i的2^i，然后給那些多擴展出來的節(jié)點的最小值設(shè)置成無窮大，最大值設(shè)置成負(fù)無窮大，則不會影響線段樹計算

設(shè)一開始輸入的規(guī)模為n_，然后線段樹葉子節(jié)點數(shù)量為n（一定需要為2的次冪），設(shè)輸入的數(shù)組為num，線段樹最大值datMax，最小值為datMin，為計算葉子節(jié)點對應(yīng)的數(shù)組下標(biāo)，可以用 i - n + 1，其中 i 是線段樹節(jié)點的下標(biāo)， i - n + 1是數(shù)組的下標(biāo)，對于i - n + 1<n_ 的datMax[i]=num[i-n+1]，datMin[i]=num[i-n+1]，對于 i - n + 1 >= n_的，datMax[i]= (-1) * inf，datMin[i]= inf

然后計算父節(jié)點的時候，那就 datMin[i]=min(datMin[i * 2 + 1] , datMin[i * 2 + 2])，datMax[i]=max(datMax[i * 2 + 1] , datMax[i * 2 + 2])即可。

然后判斷是否為葉子節(jié)點，就看 i 是不是大于 n -?1即可（n不是輸入的規(guī)模，而是大于輸入規(guī)模n_的第一個 2^i）

構(gòu)建樹的時候從 i=2*n-2;i>=0;i--即可。

然后查詢L R的時候，只需要從根節(jié)點開始進(jìn)行如下三個步驟，可以設(shè)最終用到的最小值為mint，最大值為maxt，然后設(shè)置mint=inf,maxt=inf * (-1)

1、節(jié)點 i 的區(qū)間如果與 L 和 R 毫無關(guān)聯(lián)，則return

2、節(jié)點 i 區(qū)間被 L 和 R 完全包含，則mint=min(datMin[i],mint),maxt=max(datMax[i],maxt)

3、節(jié)點 i 與區(qū)間有重合部分，但不完全包含，遞歸 i * 2 + 1 和 i * 2 + 2

然后輸出 maxt - mint即可解題

我寫線段樹時候，比較喜歡直接用數(shù)組，然后每個節(jié)點維護(hù)的區(qū)間為 左閉右開，比如 [0,1) [0,2) [0,4)，然后我習(xí)慣于把最大區(qū)間弄成 2 的次冪，之后用無窮大和負(fù)無窮大來補充不足的值 ，之后區(qū)間通過調(diào)用方法時的參數(shù)傳遞，根節(jié)點 0 的區(qū)間為 [0 , n)，然后如果節(jié)點 i 的區(qū)間為[L , R]，則它左孩子 i * 2 + 1的區(qū)間為[0 , (L?+ R) / 2] ，右孩子的區(qū)間為 [(L?+ R) / 2, R)，如果葉子節(jié)點數(shù)量時2的次冪，這個區(qū)間的計算可以通過畫個圖看出來?，如下圖所示。

然后另外補充一點，我覺得線段樹葉子大小還是要擴充到2^i，不然葉子節(jié)點的賦值容易出問題，就是用循環(huán)方式，從2*n - 2到0用i--?初始化的時候，一定會出問題，如下所示。

因為葉子節(jié)點不一定是下標(biāo)最大的幾個節(jié)點，也不一定是 i >= n - 1的節(jié)點，所以循環(huán)方式初始化有問題，但是使用遞歸初始化的話，不會有問題，而且代碼看起來更精簡。

不過還是建議把線段樹的葉子節(jié)點擴充到最接近的 2的次冪，這樣的話每一層的節(jié)點維護(hù)的區(qū)間是一樣長的，更規(guī)范。

2、平方分割

平方分割的話，就簡單很多了，我計算了下 根號 50000是 224再多一點，所以直接定義230個桶，設(shè)桶的大小為根號n下取整，定義為B，然后第 i 個桶維護(hù)的區(qū)間是?[i * B,(i + 1) * B)，如果 i * B < n，但是 (i + 1) * B大于 n 時，那么桶 i 維護(hù)的區(qū)間為 [ i * B , n)，然后維護(hù)每個桶的最大值和最小值。

設(shè)每個桶的最小值bucketMin，最大值為bucketMax，最開始把滿足 i * B < n范圍內(nèi)所有的bucketMax[i]=inf*(-1)，bucketMin[i]=inf，（我將區(qū)間從0開始，左閉右開，則n-1為最后一個有效位置，當(dāng)i * B ==?n則，代表第 i 個桶的起點維護(hù)的是數(shù)組里不存在的元素，所以 i * B < n為范圍）初始化的時候，只需用 i 循環(huán) num 數(shù)組

1、bucketMax[i / B]=max(bucketMax[i / B] , num[i])

2、bucketMin[i / B]=max(bucketMin[i / B] , num[i])

然后對于每一次輸入的 [L , R]區(qū)間，我們把它變成左閉右開，初始位置從0開始，即 L--，R不變，然后設(shè)置兩個變量 mint = inf,maxt= inf * (-1)（inf是無窮大，定義成 0x3f3f3f3f就行）

用一個數(shù)組bucketQue記錄包含在區(qū)間里的桶，設(shè)它的長度為queLen，初始化為 0

在 i * B < n 的范圍內(nèi)循環(huán)所有的桶，計算桶的區(qū)間左邊bucketL = i * B，區(qū)間右邊?bucketR = (i + 1)*B，然后bucketR > n 時，bucketR = n，如果 [bucketL , bucketR)被 [L?, R)完全包含，則

1、mint = min(mint , bucketMin[i])

2、maxt = max(maxt , bucketMax[i])

3、bucketQue[queLen++] = i

然后處理不在桶內(nèi)的區(qū)間，如果 queLen==0，則區(qū)間內(nèi)不完整包含任何一個桶，則循環(huán) [L , R)

1、mint = min(mint , num[i])

2、maxt = max(maxt ,num[i])

如果queLen>0，則循環(huán) [L , bucketQue[0] * B) 和 [(bucketQue[queLen - 1] + 1) * B) , R)

1、mint = min(mint , num[i])

2、maxt = max(maxt ,num[i])

不難看出，bucketQue[0]是第一個桶，bucketQue[0] * B是第一個桶的起點（包含）

bucketQue[queLen - 1]是最后一個桶，bucketQue[queLen - 1]是最后一個桶的終點（不包含）

所以這兩段左閉右開的區(qū)間是不包含在桶內(nèi)的，而且在區(qū)間內(nèi)的邊緣，需要計算。

然后輸出 maxt - mint即可。

三、代碼

1、線段樹（循環(huán)方式初始化，初始化葉子節(jié)點大小為 2的次冪）

#include <iostream>
using namespace std;
int datTall[131080], datShort[131080], n, n_, num[50007], inf = 0x3f3f3f3f, minShort, maxTall;
void input()
{for (int i = 0; i < n_; i++){scanf("%d", &num[i]);}
}
void init()
{n = 1;while (n < n_){n = n * 2;}for (int i = (2 * n - 2); i >= 0; i--){if (i >= (n - 1)){if ((i - n + 1) < n_){datTall[i] = num[i - n + 1];datShort[i] = num[i - n + 1];}else{datTall[i] = -inf;datShort[i] = inf;}}else{int lch = i * 2 + 1;int rch = i * 2 + 2;datTall[i] = max(datTall[lch], datTall[rch]);datShort[i] = min(datShort[lch], datShort[rch]);}}
}
void query(int l_, int r_, int i, int l, int r)
{if (l_ >= r || r_ <= l){}else if (l >= l_ && r <= r_){minShort = min(minShort, datShort[i]);maxTall = max(maxTall, datTall[i]);}else{query(l_, r_, i * 2 + 1, l, (l + r) / 2);query(l_, r_, i * 2 + 2, (l + r) / 2, r);}
}
int main()
{int m, L, R;scanf("%d%d", &n_, &m);input();init();while (m--){scanf("%d%d", &L, &R);minShort = inf;maxTall = -inf;query(L - 1, R, 0, 0, n);printf("%d\n", maxTall - minShort);}return 0;
}

2、平方分割

#include <iostream>
#include <algorithm>
using namespace std;
int datTall[230], datShort[230], num[50007], n, B, inf = 0x3f3f3f3f, bucketQue[230], queLen;
void input()
{B = 1;while (B * B <= n){B++;}B--;for (int i = 0; (i * B) < n; i++){datTall[i] = -inf;datShort[i] = inf;}for (int i = 0; i < n; i++){scanf("%d", &num[i]);datTall[i / B] = max(datTall[i / B], num[i]);datShort[i / B] = min(datShort[i / B], num[i]);}
}
void solve(int L, int R)
{queLen = 0;int minTall = inf, maxTall = -inf;for (int i = 0; (i * B) < n; i++){int bucketL = i * B;int bucketR = (i + 1) * B;bucketR = (bucketR > n ? n : bucketR);if (bucketL >= L && bucketR <= R){bucketQue[queLen++] = i;minTall = min(minTall, datShort[i]);maxTall = max(maxTall, datTall[i]);}}if (queLen == 0){for (int i = L; i < R; i++){minTall = min(minTall, num[i]);maxTall = max(maxTall, num[i]);}}else{for (int i = L; i < (bucketQue[0] * B); i++){minTall = min(minTall, num[i]);maxTall = max(maxTall, num[i]);}for (int i = ((bucketQue[queLen - 1] + 1) * B); i < R; i++){minTall = min(minTall, num[i]);maxTall = max(maxTall, num[i]);}}printf("%d\n", maxTall - minTall);
}
int main()
{int m, L, R;scanf("%d%d", &n, &m);input();while (m--){scanf("%d%d", &L, &R);solve(L - 1, R);}return 0;
}

3、線段樹（遞歸方式初始化，非完美二叉樹，代碼簡潔）

#include <istream>
using namespace std;
int datShort[131080], datTall[131080], n, num[50009], inf = 0x3f3f3f3f, mint, maxt;
void input()
{for (int i = 0; i < n; i++){scanf("%d", &num[i]);}
}
void build(int i, int l, int r)
{if (r - l == 1){datShort[i] = num[l];datTall[i] = num[l];}else{int lch = i * 2 + 1;int rch = i * 2 + 2;build(lch, l, (l + r) / 2);build(rch, (l + r) / 2, r);datShort[i] = min(datShort[lch], datShort[rch]);datTall[i] = max(datTall[lch], datTall[rch]);}
}
void query(int l_, int r_, int i, int l, int r)
{if (l_ >= r || r_ <= l){}else if (l >= l_ && r <= r_){mint = min(mint, datShort[i]);maxt = max(maxt, datTall[i]);}else{query(l_, r_, i * 2 + 1, l, (l + r) / 2);query(l_, r_, i * 2 + 2, (l + r) / 2, r);}
}
int main()
{int m, L, R;scanf("%d%d", &n, &m);input();build(0, 0, n);while (m--){scanf("%d%d", &L, &R);mint = inf, maxt = -inf;query(L - 1, R, 0, 0, n);printf("%d\n", maxt - mint);}return 0;
}