C++如何快速求同一数列中多个区间的最大值？ |21xrx.com

C++如何快速求同一数列中多个区间的最大值？

2023-07-05 07:31:59 深夜i -- --

C++ 数列区间最大值求解

在C++中，我们可以使用STL中的数据结构——线段树来实现快速求同一数列中多个区间的最大值。线段树是一棵二叉树，每个节点代表数列中的一个区间。它的叶子节点代表数列中的单个元素。线段树的特点是能够在O(log n)的时间复杂度内对数列中多个区间进行查询和修改操作。

在实现过程中，我们首先需要定义线段树节点的结构体。由于我们需要求区间的最大值，因此我们需要记录区间中的最大值和区间的左右端点。

 C++
struct Node r;
  int maxn;
;

接下来，我们需要实现线段树的建树函数。建树函数需要递归地将区间分成左右两个子区间，并将每个子区间对应的节点连接到父节点上。在这个过程中，我们需要记录每个节点的左右端点。

 C++
void build(int p, int l, int r){
  if(l == r){
    tree[p].l = tree[p].r = l;
    tree[p].maxn = a[l];
    return;
  }
  tree[p].l = l;
  tree[p].r = r;
  int mid = (l + r) / 2;
  build(p * 2, l, mid);
  build(p * 2 + 1, mid + 1, r);
  tree[p].maxn = max(tree[p * 2].maxn, tree[p * 2 + 1].maxn);
}

在建树后，我们可以实现查询函数。查询函数也是递归实现的。我们需要将查询区间与节点表示的区间进行比较，有三种情况：

1. 查询区间包含了节点表示的区间，返回节点的最大值。

2. 查询区间与节点表示的区间没有交集，返回无穷小。

3. 查询区间与节点表示的区间有交集，递归查询左右子节点，并返回最大值。

 C++
int query(int p, int l, int r){
  if(l <= tree[p].l && tree[p].r <= r){
    return tree[p].maxn;
  }
  if(r < tree[p].l || tree[p].r < l)
    return INT_MIN;
  
  return max(query(p * 2, l, r), query(p * 2 + 1, l, r));
}

最后，我们可以在主函数中调用建树函数，并可以在需要查询区间最大值的位置调用查询函数。

 C++
int main(){
  int n, m;
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i++){
    scanf("%d", &a[i]);
  }
  build(1, 1, n);
  for(int i = 1; i <= m; i++){
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d\n", query(1, l, r));
  }
  return 0;
}

使用线段树求同一数列中多个区间的最大值，可以大大提高程序的效率。当需要查询不同的区间时，不需要重复计算，也能保证查询时间复杂度始终为O(log n)。因此，在需要频繁操作数列区间的情况下，使用线段树是非常优秀的选择。

上一篇: idea打包java可执行jar包

下一篇: "C/C++程序员面试指南下载"

评论区

()

相似文章