【Algorithm Notes】【Special Topic】RMQ Problems: Sparse Table/Fenwick Tree/Segment Tree

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…

TLE on one test case

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[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

$$ 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;  
}

AC

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;  
}

AC

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;  
}

AC

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!

© 2020 - 2025 GoodCoder's Blog
Built with Hugo
Theme Stack designed by Jimmy