数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学线段树 | 区间最小值查询
线段树 - 线段树是一种用于存储区间和线段的树形数据结构。它是一种静态结构，即一旦构建就无法修改。线段树用于处理数组或类似线性数据结构上的区间查询。
在线段树中，我们将输入数组划分为多个线段，并预计算这些线段的值。线段树中的每个节点都表示数组的一个区间或线段。根节点表示整个数组，每个子节点表示由父节点划分形成的线段。这种划分最终导致叶节点表示数组的单个元素。
用于区间和查询的线段树 -
Original Array: [7, 1, 2, 3, 6, 5, 0, 4]
Segment Tree:
38
/ \
13 25
/ \ / \
8 5 11 4
/ \ / \ / \ / \
7 1 2 3 6 5 0 4
线段树的每个区间查询和更新操作的复杂度为 O(logN)。
区间最小值查询 - RMQ 是一种常见问题，对于给定的数组，我们需要找到指定区间内的最小元素。线段树是解决此问题的最高效的数据结构。
问题陈述
给定一个包含 N 个元素的整数数组 arr[] 以及起始和结束索引。任务是找到位于 [start, end] 范围内的元素中的最小元素。
示例 1
输入
N = 8
arr[] = {1, 7, 8, 9, 5, 2, 3, 4}
start = 2
end = 6
输出
2
解释
Array within the specified range is: {8, 9, 5, 2, 3}
在给定范围内，2 是最小元素。
示例 2
输入
N = 3
arr[] = {1, 3, 2}
start = 1
end = 1
输出
3
解释
Array within the specified range is: {3}
在给定范围内，3 是最小元素。
解决方案
区间最小值查询问题可以通过以下步骤解决：
为输入数组构建线段树。
递归查找树中包含在查询中的线段。每个线段可以归类为以下几种情况之一：
完全重叠 - 当前线段完全在查询范围内。
无重叠 - 当前线段完全在查询范围之外。
部分重叠 - 当前线段部分覆盖查询范围。
构建线段树的伪代码
function segmentTreeUtil(arr, seg_start, seg_end, tree, curr)
if seg_start == seg_end then
tree[curr] = arr[seg_start]
return arr[seg_start]
mid = getMid(seg_start, seg_end)
tree[curr] = minVal(segmentTreeUtil(arr, seg_start, mid, tree, curr * 2 + 1), segmentTreeUtil(arr, mid + 1, seg_end, tree, curr * 2 + 2))
return tree[curr]
end function
function segmentTree(arr, n)
x = ceil(log2(n))
max_size = 2 * (2^x) - 1
tree = new int[max_size]
segmentTreeUtil(arr, 0, n - 1, tree, 0)
return tree
end function
RMQ 的伪代码
function RMQUtil(tree, seg_start, seg_end, start, end, index)
if start <= seg_start and end >= seg_end then
return tree[index]
if seg_end < start or seg_start > end then
return INT_MAX
end function
mid = getMid(seg_start, seg_end)
return minVal(RMQUtil(tree, seg_start, mid, start, end, 2 * index + 1), RMQUtil(tree, mid + 1, seg_end, start, end, 2 * index + 2))
function RMQ(tree, n, start, end)
if start < 0 or end > n - 1 or start > end then
print "Query Range Invalid"
return -1
return RMQUtil(tree, 0, n - 1, start, end, 0)
end function
示例：C++ 实现
以下代码构建一个线段树来解决 RMQ 问题。
#include <bits/stdc++.h>
using namespace std;
int minVal(int x, int y){
return (x < y) ? x : y;
}
int getMid(int x, int y){
return x + (y - x) / 2;
}
// Recursive function used to find the minimum element in the query range
int RMQUtil(int *tree, int seg_start, int seg_end, int start, int end, int index){
// Complete Overlap
if (start <= seg_start && end >= seg_end)
return tree[index];
// No Overlap
if (seg_end < start || seg_start > end)
return INT_MAX;
// Partial Overlap
int mid = getMid(seg_start, seg_end);
return minVal(RMQUtil(tree, seg_start, mid, start, end, 2 * index + 1), RMQUtil(tree, mid + 1, seg_end, start, end, 2 * index + 2));
}
// Calculates RMQ by calling RMQUtil()
int RMQ(int *tree, int n, int start, int end){
if (start < 0 || end > n - 1 || start > end){
cout << "Query Range Invalid";
return -1;
}
return RMQUtil(tree, 0, n - 1, start, end, 0);
}
// Creates Segment Tree for input array
int segmentTreeUtil(int arr[], int seg_start, int seg_end, int *tree, int curr){
// Base Case of only one element in array
if (seg_start == seg_end) {
tree[curr] = arr[seg_start];
return arr[seg_start];
}
// Dividing array into segments
int mid = getMid(seg_start, seg_end);
tree[curr] = minVal(segmentTreeUtil(arr, seg_start, mid, tree, curr * 2 + 1), segmentTreeUtil(arr, mid + 1, seg_end, tree, curr * 2 + 2));
return tree[curr];
}
// Creates Segment Tree by allocating memmory and calling segmentTreeUtil()
int *segmentTree(int arr[], int n){
int x = (int)(ceil(log2(n)));
int max_size = 2 * (int)pow(2, x) - 1;
int *tree = new int[max_size];
segmentTreeUtil(arr, 0, n - 1, tree, 0);
return tree;
}
int main(){
int arr[] = {1, 7, 8, 9, 5, 2, 3, 4};
int n = 8;
int *tree = segmentTree(arr, n);
int start = 2;
int end = 6;
cout << "Minimum value = " << RMQ(tree, n, start, end) << endl;
return 0;
}
输出
Minimum value = 2
时间复杂度 - 构建树的时间复杂度为 O(N)，每个 RMQ 的时间复杂度为 O(logn)。因此，对于 Q 个查询，时间复杂度为 O(Q*logN)。
空间复杂度 - O(N)
结论
总之，使用线段树的区间最小值查询 (RMQ) 是一种高效的数据结构和算法，用于查找数组给定范围内的最小元素。每个查询的时间复杂度为 O(logN)，优于具有 O(N) 复杂度的朴素遍历数组的方法。
更新于：2023-11-03
780 次浏览
广告