Translation Notice
This article was machine-translated using DeepSeek-R1.
- Original Version: Authored in Chinese by myself
- Accuracy Advisory: Potential discrepancies may exist between translations
- Precedence: The Chinese text shall prevail in case of ambiguity
- Feedback: Technical suggestions regarding translation quality are welcomed
Preface
It’s been a while since the last update to the algorithm notes column. Just learned a new algorithm, so here’s an update…
This is also the first special topic of this column, covering three data structures. If you spot any issues, please feel free to point them out. Thanks!
About RMQ Problems
RMQ stands for Range Minimum/Maximum Query.
In this article, our algorithms focus on finding maximum values (minimum values follow similar logic). The problem statement is as follows:
Given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$.
There are $Q$ queries. The $i$-th query is:
$\to~$ Given $1\le l_i\le r_i\le N$, find the maximum value in interval $[l_i,r_i]$, i.e., $\displaystyle\max_{j=l_i}^{r_i} A_j$.
Below, we’ll start with a brute-force approach and gradually introduce common solutions for RMQ problems.
Standard RMQ problems (all algorithms except brute-force can pass):
Solutions
Brute-Force
We first read the sequence $A$, then process each query by directly iterating through $A_l\dots A_r$.
Time complexity: $\mathcal O(\sum r_i-l_i)=\mathcal O(NQ)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include <cstdio>
#define maxn 100005
using namespace std;
int a[maxn];
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for(int i=0; i<n; i++)
scanf("%d", a + i);
while(q--)
{
int l, r;
scanf("%d%d", &l, &r);
l --, r --;
int res = a[l];
for(int i=l+1; i<=r; i++)
if(a[i] < res)
res = a[i];
printf("%d ", res);
}
return 0;
}
|
However, when submitting to Luogu P1816…
Clearly, the time complexity is too high. Further optimization is needed.
Sparse Table
Sparse Table (ST) is a data structure for static RMQ problems.
Static means the original sequence remains unchanged. ST tables cannot handle direct modifications.
ST table initialization takes $\mathcal O(N\log N)$, and each query takes $\mathcal O(1)$.
Storage Structure
ST table is essentially a 2D array of size $N\times\lceil\log N\rceil$, defined as:
$$
st[i][j]=\max\{A_i,A_{i+1},\dots,A_{i+2^j-1}\}
$$
Here, $st[i][j]$ represents the maximum value of $2^j$ elements starting from $A_i$, using a doubling strategy.
Initialization
Fill the table using a DP-like approach:
$$
st[i][j]=\max\{st[i][j-1],st[i+2^{j-1}][j-1]\}
$$
Fill by iterating $j$ first, then $i$. Total initialization time: $\mathcal O(N\log N)$.
Pseudocode:
1
2
3
4
5
6
7
|
function init() {
for i = 1 to N
st[i][0] = A[i]
for j = 1 to log2(N)
for i = 1 to (N + 1 - 2^j)
st[i][j] = max(st[i][j - 1], st[i + 2^(j-1)][j - 1])
}
|
C++ implementation:
1
2
3
4
5
6
7
8
|
void init()
{
for(int i=0; i<n; i++)
st[i][0] = A[i];
for(int j=1; j<=log2(n); j++)
for(int i=0; i+(1<<j)<=n; i++) // Note: <=n
st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
|
Query
For interval $[l,r)$, find two intervals $[l,a)$ and $[b,r)$ such that their union is exactly $[l,r)$. Let $k=\lfloor\log_2(r-l)\rfloor$:
1
2
3
4
5
6
|
// query(l, r) = max(A[l], ..., A[r - 1])
inline int query(int l, int r)
{
int k = log2(r - l);
return max(st[l][k], st[r - (1 << k)][k]);
}
|
Full Implementation
Complete code for Luogu P1816. Time complexity: $\mathcal O(Q+N\log N)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <cstdio>
#include <cmath>
#include <algorithm>
#define maxn 100005
using namespace std;
int st[maxn][17]; // 2^17=131072
void init(int n)
{
for(int j=1, t=log2(n); j<=t; j++)
for(int i=0; i+(1<<j)<=n; i++)
st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
inline int query(int l, int r)
{
int k = log2(r - l);
return min(st[l][k], st[r - (1 << k)][k]); // Note: min for this problem
}
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for(int i=0; i<n; i++)
scanf("%d", st[i]); // Directly read into ST table
init(n);
while(q--)
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d ", query(--l, r));
}
return 0;
}
|
Runtime: $128\mathrm{ms}$
Memory: $6.90\mathrm{MB}$
Fenwick Tree
For Fenwick Tree basics, see this article. Here, we adapt it for RMQ.
Original Algorithm
Fenwick Tree supports prefixSum and update in $\mathcal O(\log N)$. It works for any associative operation.
Implementing prefixMax and update:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#define INF 2147483647
#define lowbit(x) ((x) & -(x))
inline void setmax(int& x, int y) { if(y > x) x = y; }
int n, A[N], bit[N];
// max(A[1], ..., A[i])
inline int prefixMax(int i)
{
int res = -INF;
for(; i>0; i-=lowbit(i))
setmax(res, bit[i]);
return res;
}
// A[i] = max(A[i], val)
inline void update(int i, int val)
{
for(; i<=n; i+=lowbit(i))
setmax(bit[i], val);
}
|
RMQ Fenwick Tree
Define recursive rangeMax:
1
2
3
4
5
6
7
8
|
int rangeMax(int l, int r)
{
if(l == r) return A[l];
int t = r - lowbit(r);
return t < l?
max(A[r], rangeMax(l, r - 1)):
max(bit[r], rangeMax(l, t));
}
|
Non-recursive version for efficiency:
1
2
3
4
5
6
7
8
9
10
11
|
int rangeMin(int l, int r)
{
int res = INF;
while(l <= r)
{
int t = r - lowbit(r);
if(t < l) setmin(res, a[r--]);
else setmin(res, bit[r]), r = t;
}
return res;
}
|
Full Implementation
Solution for Luogu P1816. Time complexity: $\mathcal O(N+Q\log N)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <cstdio>
#define maxn 100005
using namespace std;
#define INF 2147483647
#define lowbit(x) ((x) & -(x))
inline void setmin(int& x, int y) { if(y < x) x = y; }
int a[maxn], bit[maxn];
int rangeMin(int l, int r)
{
int res = INF;
while(l <= r)
{
int t = r - lowbit(r);
if(t < l) setmin(res, a[r--]);
else setmin(res, bit[r]), r = t;
}
return res;
}
inline void init(int n)
{
for(int i=1; i<=n; i++)
bit[i] = a[i];
for(int i=1; i<=n; i++)
{
int j = i + lowbit(i);
if(j <= n) setmin(bit[j], bit[i]);
}
}
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for(int i=1; i<=n; i++)
scanf("%d", a + i);
init(n);
while(q--)
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d ", rangeMin(l, r));
}
return 0;
}
|
Runtime: $135\mathrm{ms}$
Memory: $1.14\mathrm{MB}$
Segment Tree
Segment Trees handle a wider range of problems with $\mathcal O(N)$ initialization and $\mathcal O(\log N)$ per query.
Storage Structure
Stored as a heap-like array. Each node represents an interval.
1
2
3
|
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define par(x) (x >> 1)
|
Build
Recursively construct left and right subtrees:
1
2
3
4
5
6
7
8
9
10
11
12
|
void build(int l, int r, int p)
{
if(l == r)
{
c[p] = a[l];
return;
}
int m = l + r >> 1;
build(l, m, ls(p));
build(m + 1, r, rs(p));
c[p] = min(c[ls(p)], c[rs(p)]);
}
|
Query
Recursively check overlapping intervals:
1
2
3
4
5
6
7
8
|
int query(int l, int r, int a, int b, int p)
{
if(a <= l && r <= b) return c[p];
int m = l + r >> 1, res = INF;
if(m >= a) res = min(res, query(l, m, a, b, ls(p)));
if(m < b) res = min(res, query(m + 1, r, a, b, rs(p)));
return res;
}
|
Full Implementation
Solution for Luogu P1816. Time complexity: $\mathcal O(N+Q\log N)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include <cstdio>
#include <algorithm>
#define maxn 100005
using namespace std;
#define INF 2147483647
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define par(x) (x >> 1)
int a[maxn], c[maxn << 2];
void build(int l, int r, int p)
{
if(l == r)
{
c[p] = a[l];
return;
}
int m = l + r >> 1;
build(l, m, ls(p));
build(m + 1, r, rs(p));
c[p] = min(c[ls(p)], c[rs(p)]);
}
int query(int l, int r, int a, int b, int p)
{
if(a <= l && r <= b) return c[p];
int m = l + r >> 1, res = INF;
if(m >= a) res = min(res, query(l, m, a, b, ls(p)));
if(m < b) res = min(res, query(m + 1, r, a, b, rs(p)));
return res;
}
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for(int i=0; i<n; i++)
scanf("%d", a + i);
build(0, n - 1, 1);
while(q--)
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d ", query(0, n - 1, --l, --r, 1));
}
return 0;
}
|
Runtime: $163\mathrm{ms}$
Memory: $1.78\mathrm{MB}$
Summary
Comparison of algorithms:
| Algorithm |
Preprocessing Time |
Query Time |
Space |
Passes Constraints? |
| Brute-Force |
$\mathcal O(1)$ |
$\mathcal O(N)$ |
$\mathcal O(N)$ |
❌ |
| Sparse Table |
$\mathcal O(N\log N)$ |
$\mathcal O(1)$ |
$\mathcal O(N\log N)$ |
✔️ |
| Fenwick Tree |
$\mathcal O(N)$ |
$\mathcal O(\log N)$ |
$\mathcal O(N)$ |
✔️ |
| Segment Tree |
$\mathcal O(N)$ |
$\mathcal O(\log N)$ |
$\mathcal O(N)$ |
✔️ |
Performance on Luogu P1816:
| Algorithm |
Runtime |
Memory |
Code Length |
| Sparse Table |
$128\mathrm{ms}$ |
$6.90\mathrm{MB}$ |
$625\mathrm B$ |
| Fenwick Tree (non-recursive) |
$135\mathrm{ms}$ |
$1.14\mathrm{MB}$ |
$786\mathrm B$ |
| Segment Tree |
$163\mathrm{ms}$ |
$1.78\mathrm{MB}$ |
$905\mathrm B$ |
ST Table is fastest but memory-heavy. Fenwick Tree balances speed and space. Segment Tree is versatile but slightly slower.
This concludes the article. Hope you found it helpful!
This is my first 10k-word article in 2023. Happy New Year!