APPLIED ALGORITHMS

APPLIED ALGORITHMS
Data structures and advanced techniques:
Range Minimum Query, Segment Trees

3
CONTENTS

• Range Minimum Query (cấu trúc truy vấn phần tử nhỏ nhất trên đoạn con)
• Segment tree (cấu trúc cây phân đoạn)

4
Range Minimum Query (RMQ)

• Illustrative exercise (P.02.03.01). Given the sequence a0, a1, …, aN-1 and a positive integer K. We
need to perform K queries, each query of the form RMQ(i, j) returns the index of the smallest
element of the sequence ai, ai+1, . . ., aj.

5
Range Minimum Query (RMQ)

• Illustrative exercise (P.02.03.01). Given the sequence a0, a1, …, aN-1 and a positive integer K. We
need to perform K queries, each query of the form RMQ(i, j) returns the index of the smallest
element of the sequence ai, ai+1, . . ., aj. RMQ(a, i, j){
• Direct algorithm min = +; min_idx = -1;
• For each query RMQ(i, j): traverse sequence ai, ai+1, . . ., aj. for k = i to j do {
• Complexity O(j - i) if min > a[k] then {
min = a[k];, min_idx = k;
}
}
return min_idx;
}

6
Range Minimum Query (RMQ)

• Illustrative exercise (P.02.03.01). Given the sequence a0, a1, …, aN-1 and a positive integer K. We
need to perform K queries, each query of the form RMQ(i, j) returns the index of the smallest
element of the sequence ai, ai+1, . . ., aj.
• Preprocess
• Calculate M[i,j] as the index of the smallest element of the subsequence starting from aj and
having 2i elements, where i = 0, 1, 2, …, log2(N+1) and j = 0, 1, 2, …, N-1.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 4 6 1 6 8 7 3 3 5 8 9 1 2 6 4

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 0 1 3 3 4 6 7 8 8 9 10 12 12 13 15 -
2 3 3 3 3 7 8 8 8 8 12 12 12 12 - - -
3 3 3 3 3 8 12 12 12 12 - - - - - - -
4 12 - - - - - - - - - - - - - - -

7
Range Minimum Query (RMQ)

• The smallest subproblem: M[0, j] = j, j = 0,…, N-1

• Recursive formula
M[i, j] = M[i-1, j] if a[M[i-1, j]] < a[M[i-1, j+2i-1]
M[i-1, j+2i-1], otherwise
j j+2i-1 -1
j + 2i -1 j + 2i - 1

M[i-1, j] M[i-1, j + 2i -1]

M[i, j]

8
Range Minimum Query (RMQ)

• The smallest subproblem: M[0, j] = j, j = 0,…, N-1

• Recursive formula preprocessing(){
for (i = 0; i < N; i++) M[0,i] = i;
M[i, j] = M[i-1, j] if a[M[i-1, j]] < a[M[i-1, j+2i-1]
M[i-1, j+2i-1], otherwise for (j = 0; 2j ≤ N; j++){
for(i = 0; i + 2j -1 < N; i++){
if a[M[j-1,i]] < a[M[j-1,i+2j-1]] then{
M[j,i] = M[j-1,i];
}else{
M[j,i] = M[j-1,i+2j-1];
}
}
}
}

9
Range Minimum Query (RMQ)

• Query RMQ(i,j)
• k = [log(j-i+1)]
• RMQ(i,j) = M[k,i] if a[M[k,i]] ≤ a[M[k, j-2k+1]]
M[k, j-2k+1]], otherwise
• RMQ(4,14) = ?
• k = [log(14-4+1)]=3
• a[7] > a[12] → RMQ(4,14) = 12 M[3,7] = 12

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

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

M[3,4] = 7

10
SEGMENT TREES (CÂY PHÂN ĐOẠN)

• Illustrative exercise (P.02.03.02). Given the sequence a1, a2, . . ., an. Perform a series of the
following operations on the given sequence:
• update i v: assign ai = v
• get-max i j: return the largest value in the sequence ai, ai+1, . . ., aj.

11
SEGMENT TREES (CÂY PHÂN ĐOẠN)

• Illustrative exercise (P.02.03.02). Given the sequence a1, a2, . . ., an. Perform a series of the
following operations on the given sequence:
• update i v: assign ai = v
• get-max i j: return the largest value in the sequence ai, ai+1, . . ., aj.
• Direct algorithm
• Operation update i v: upadate ai = v, complexity O(1)
• Operation get-max i j: traverse sequence ai, ai+1, . . ., aj to find the largest element, complexity
O(j – i)

12
SEGMENT TREES (CÂY PHÂN ĐOẠN)

• Segment Trees: full binary tree (cấu trúc cây nhị phân đầy đủ)
• Each node manages a segment in the tree
• Root node with id = 1 manages the segment with index [1, n]
• Each node with id = v manages the segment with index [i, j], then
• Left child node with id = 2v manages the segment with index [i, (i+j)/2]
• Right child node with id = 2v+1 manages the segment with index [(i+j)/2+1, j]
• Data structure represents each node of the tree
id, [L, R], maxVal[id]
• id: index of the node
• L and R: start index and end index of subsequence aL, aL+1, . . ., aR that the node manages
• maxVal[id]: the largest value of subsequence aL, aL+1, . . ., aR that the node manages

13
 SEGMENT TREES (CÂY PHÂN ĐOẠN)

1 2 3 4 5 6 7 8
1, [1, 8], 9
5 3 7 6 9 2 8 4

2, [1, 4], 7 3, [5, 8], 9

4, [1, 2], 5 5, [3, 4], 7 6, [5, 6], 9 7, [7, 8], 8

8, [1, 1], 5 9, [2, 2], 3 10, [3, 3], 7 11, [4, 4], 6 12, [5, 5], 9 13, [6, 6], 2 14, [7, 7], 8 15, [8, 8], 4

14
SEGMENT TREES (CÂY PHÂN ĐOẠN)

GetMaxFromNode(id, L, R, i, j){
// return the max value of ai,. . ., aj from the node (id, L, R)
if i > R or j < L then return -; // [L, R] and [i, j] are disjoint → not found
if i <= L and j >= R then // [L, R] is within [i, j]
return maxVal[id] // max value is stored in the node (id, L, R)
m = (L + R)/2;
LC = 2*id; RC = 2*id+1; // left-child and right-child
maxLeft = GetMaxFromNode(LC, L, m, i, j);
maxRight = GetMaxFromNode(RC, m+1, R, i, j);
return max(maxLeft, maxRight);
}
GetMax(i, j){
return GetMaxFromNode(1, 1, n, i, j) // Find Max from the root node
}

15
SEGMENT TREES (CÂY PHÂN ĐOẠN)

UpdateFromNode(id, L, R, index, value){

// propagate from the node (id, L, R) by the update: a[index] = value
if L > R then return;
if index < L or index > R then return; // node (id, L, R) does not manage a[index]
if L == R then { maxVal[id] = value; return; }
LC = 2*id; RC = 2*id + 1; // left-child and right-child
m = (L+R)/2;
UpdateFromNode(LC, L, m, index, value);
UpdateFromNode(RC, m+1, R, index, value);
maxVal[id] = max(maxVal[LC], maxVal[RC]);
}
Update(i, v){
UpdateFromNode(1, 1, n, i, v) // start the propagation from the root node
}

16
SEGMENT TREES (CÂY PHÂN ĐOẠN)

• The number of nodes on the segment tree is less than or equal to 4n

• Denote k = logn
• The maximum number of nodes in the tree is 1 + 21 + 22 + . . . + 2k = 2k+1 – 1 < 4n

17
SEGMENT TREES (CÂY PHÂN ĐOẠN)

• The complexity of the GetMax operation: we will traverse at most 4 nodes on each level of the tree
(prove by induction)
• At level 1 (at root node): we only traverse the root node
• Suppose we are at a current level k, we visit nodes Vk (|Vk|  4)
• We call two segments [a, b] and [c, d] over-lap with each other if this segment is not a subsegment
(or equal) of the other segment.
• Note: In the function GetMaxFromNode(id, L, R, i, j) at node (id, L, R), we only have recursive call to
traverse the child node if the segments [L, R] và [i, j] are over- lap.
• Suppose the nodes in Vk (from left to right) are (id1, L1, R1), (id2, L2, R2), …, (idq, Lq, Rq). Obviously, the
number of segments in [L1, R1], . . ., [Lq, Rq] over-lap with segment [i, j] must be ≤ 2 because otherwise,
the middle segments in this series of over-lap segments with [i, j] will definitely is a child segment (or
equal) of segment [i, j] and therefore from the nodes corresponding to the segments in the middle
there will be no recursive call to visit the child node. Thus, it can be deduced that the number of child
nodes at level k+1 traversed is less than or equal to 4.
i j

L1 R1 L2 R2 L3 R3 Lq Rq
. . .

18
SEGMENT TREES (CÂY PHÂN ĐOẠN)

• The complexity of the GetMax operation

• We will traverse at most 4 nodes on each level of the tree (prove by induction).
• The height of the tree is O(logn). Thus, the complexity of the GetMax(i, j) operation is 4 x
O(logN) or O(logN)

19
SEGMENT TREES (CÂY PHÂN ĐOẠN)

• The complexity of the Update(i, v) operation

• Starting from the root node, at each level k, we only visit at most one child node because the
index i only belongs to at most 1 subsegment among the 2 subsegments divided from the
segment at the previous level.
• Therefore, the complexity of the Update(i, v) operation is the height of the tree and is O(logn)

20
THANK YOU !

21