线段树 | 区间最小值查询

线段树 - 线段树是一种用于存储区间和线段的树形数据结构。它是一种静态结构，即一旦构建就无法修改。线段树用于处理数组或类似线性数据结构上的区间查询。

在线段树中，我们将输入数组划分为多个线段，并预计算这些线段的值。线段树中的每个节点都表示数组的一个区间或线段。根节点表示整个数组，每个子节点表示由父节点划分形成的线段。这种划分最终导致叶节点表示数组的单个元素。

用于区间和查询的线段树 -

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 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告