【海賊王的數據航海】ST表—

【海賊王的數據航海】ST表——RMQ問題

1 -> RMQ問題

1.1 -> 定義

1.2 -> 解決策略

2 -> ST表

2.1 -> 定義

2.2 什么是可重復貢獻問題

2.3 -> 預處理ST表

2.4 -> 處理查詢

2.5 -> 實際問題

1 -> RMQ問題

1.1 -> 定義

RMQ (Range Minimum/Maximum Query)即區間最值查詢問題指：有一組數據和若干個查詢，要求在短時間內回答每個查詢[ l ,r ]?內的最值。

1.2 -> 解決策略

樸素搜索：暴力(BFS/DFS) 時間復雜度O(n)。
線段樹(Segment Tree) 時間復雜度O(n)-O(logn)。
ST表(Sparse Table，稀疏表)：倍增思想，O(nlogn)預處理，O(1)查詢最值。

2 -> ST表

2.1 -> 定義

ST表(Sparse Table，稀疏表)，主要應用倍增思想，是一種用于解決可重復貢獻問題的數據結構。它通過預處理給定數組，創建一個二維表格，使得任何區間的最小/最大值查詢都可以在常數時間內完成。ST表特別適合于靜態數據：當數列不經常改變時，它是最有效的。可以實現O(nlogn)預處理、O(1)查詢。主要用于解決RMQ問題。

2.2 什么是可重復貢獻問題

可重復貢獻問題是指在某些特定的數學運算中，當運算的性質滿足一定條件時，即使是在包含重復部分的區間內進行詢問，所得到的結果仍然是相同的問題。這種問題的特點是，它們可以通過預處理所有可能的區間，然后在查詢時直接返回預處理的結果來解決。例如，最大值問題和最大公因數問題就是典型的可重復貢獻問題，因為它們滿足以下性質：

最大值滿足?max(x, x) = x
最大公因數滿足?gcd(x, x) = x

這些性質意味著，對于任何給定的數?x，其自身與其他任何數的最大值或最大公因數仍然是?x?本身。因此，當我們需要計算一個區間內的最大值或最大公因數時，可以將區間分割成更小的子區間，并利用這些子區間的結果來快速得出整個區間的答案。?

2.3 -> 預處理ST表

倍增法遞推：用兩個等長的小區間拼湊成一個大區間。

f[ i ][ j ] 以第 i 個數為起點，長度為 $2^{^{j}}$ 的區間中的最大值。

理想狀態方程： $f[ i ][ j ] = max(f[ i ][ j - 1 ], f[ i + 2^{j - 1}][j - 1])$

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>
using namespace std;const int N = 1e5 + 10;const int M = 20;int f[N][M];int main()
{//預處理ST表int n = 0;int m = 0;for (int i = 0; i < n; i++)cin >> f[i][0];for (int j = 1; j <= M; j++)  //枚舉區間長度for (int i = 1; i + (1 << j) - 1 <= n; i++)  //枚舉起點f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);return 0;
}

區間終點： $i+ 2^{j}-1\leq n$

假如n = 6

區間長度倍增：1，2，4，8……

f[ i，0 ]：[ 1 1 ][ 2 2 ][ 3 3 ][ 4 4 ][ 5 5 ][ 6 6 ]

f[ i，1?]：[ 1 2?][ 2 3?][ 3 4?][ 4 5?][ 5 6?]

f[ i，2?]：[ 1 4?][ 2 5?][ 3 6?]

$j=3:i+2^{j}-1=1+8-1>6$

2.4 -> 處理查詢

對查詢區間[ l，r ]做分割、拼湊。

區間長度的指數： $k=log_{2}(r - l + 1)$

k = 0：{1}

k = 1：{2，3}

k = 2：{4，5，6，7}

k = 3：{8，9，10，11，12，13，14，15}

通過觀察可以發現： $2^{k}\leq r-l+1< 2\cdot 2^{k}$

即區間[ l，r ]必可以用兩個長度為 $2^{k}$ 的區間重疊拼湊。

即 $max(f[l][k],f[r-2^{k}+1][k])$ ?

    int l = 0;int r = 0;for (int i = 1; i <= m; i++){scanf("%d %d", &l, &r);int k = log2(r - l + 1);  //區間長度指數printf("%d\n", max(f[l][k], f[r - (1 << k) + 1][k]));}

[1，4] -> [1，4] + [1，4]?

[1，5] -> [1，4] + [2，5]?

[1，6] -> [1，4] + [3，6]?

[1，7] -> [1，4] + [4，7]?

總結：凡是符合結合律且可重復貢獻的信息查詢都可以使用ST表。顯然最大值、最小值、最大公因數、最小公倍數、按位或、按位與都符合這個條件。如果涉及區間修改操作，就要使用線段樹解決了。?

2.5 -> 實際問題

luogu：P3865

題目鏈接：P3865 【模板】ST 表

題目背景

這是一道 ST 表經典題——靜態區間最大值

題目描述

給定一個長度為?N?的數列，和?M?次詢問，求出每一次詢問的區間內數字的最大值。

輸入格式

第一行包含兩個整數?N,M，分別表示數列的長度和詢問的個數。

第二行包含?N?個整數（記為 ai?），依次表示數列的第?i?項。

接下來?M?行，每行包含兩個整數?𝑙𝑖,𝑟𝑖，表示查詢的區間為?[𝑙𝑖,𝑟𝑖]。

輸出格式

輸出包含?M?行，每行一個整數，依次表示每一次詢問的結果。

輸入輸出樣例

輸入 #1

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

輸出 #1

說明/提示

對于?30%30%?的數據，滿足?1≤𝑁,𝑀≤101≤N,M≤10。

對于?70%70%?的數據，滿足?1≤𝑁,𝑀≤1051≤N,M≤105。

對于?100%100%?的數據，滿足?1≤𝑁≤1051≤N≤105，1≤𝑀≤2×1061≤M≤2×106，𝑎𝑖∈[0,109]ai?∈[0,109]，1≤𝑙𝑖≤𝑟𝑖≤𝑁1≤li?≤ri?≤N。

AC代碼：

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>
#include <cmath>
using namespace std;const int N = 1e5 + 10;const int M = 20;int f[N][M];int main()
{//預處理ST表int n = 0;int m = 0;scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", &f[i][0]);for (int j = 1; j <= M; j++)  //枚舉區間長度for (int i = 1; i + (1 << j) - 1 <= n; i++)  //枚舉起點f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);int l = 0;int r = 0;for (int i = 1; i <= m; i++){scanf("%d %d", &l, &r);int k = log2(r - l + 1);  //區間長度指數printf("%d\n", max(f[l][k], f[r - (1 << k) + 1][k]));}return 0;
}

感謝各位大佬支持！！！

互三啦！！！

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/41875.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/41875.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/41875.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！