Leo201111 2024-08-27 12:08 采纳率: 80.3%
浏览 4

关于线段树区间查询最小值的问题

#include<bits/stdc++.h>
const int MAXN=1E6;
int n,m,k,l,r,x,v;
int a[MAXN+1],min[MAXN+1];
#define mid ((l+r)>>1)
void build(int k,int l,int r) {
  if(l==r) {
    min[k]=a[l];
    return;
  }
  build(k*2,l,mid);
  build(k*2|1,mid+1,r);
  min[k]=std::min(min[k*2],min[k*2|1]);
}
void change(int k,int l,int r,int x,int v) {
  if(l==r) {
    min[k]+=v;
    return;
  }
  if(x<=mid)  change(k*2,l,mid,x,v);
  else
    change(k*2|1,mid+1,r,x,v);
  min[k]=std::min(min[k*2],min[k*2|1]);
}
int ask_point(int k,int l,int r,int x) {
  if(l==r)  return min[k];
  if(x<=mid)  return ask_point(k*2,l,mid,x);
  else
    return ask_point(k*2|1,mid+1,r,x);
}
int ask_min(int k,int l,int r,int x,int y) {
  if(x<=l && r<=y)  return min[k];
  int res=0x3F3F3F3F;
  if(x<=mid)  res=std::min(res,ask_min(k*2,l,mid,x,y));
  if(y>mid)  res=std::min(res,ask_min(k*2|1,mid+1,r,x,y));
  return res;
}
int main() {
  std::cin>>n>>m;
  for(int i=1;i<=n;i++)
    scanf("%d",a+i);
  build(1,1,n);
  while(m--) {
    scanf("%d",&k);
    switch(k) {
    case 0:
      scanf("%d %d",&x,&v),change(1,1,n,x,v); break;
    case 1:
      scanf("%d",&x),printf("%d\n",ask_point(1,1,n,x)); break;
    case 2:
      scanf("%d %d",&l,&r),printf("%d\n",ask_min(1,1,n,l,r)); break;
    }
  }
}

能否帮忙检查一下我这个代码,自己写的,就是用线段树实现区间求最小值,n是序列长度,m是操作次数,然后输入序列a,建线段树(数组名称min)),然后m次操作,每次操作先输入k,k=0时,输入x和v,表示将序列的第x个数加上v(单点修改);k=1时,输入x,表示查询序列的第x个数(单点查询);k=2时,输入l和r,表示查询区间[l,r]的最小值(区间查询最小值min)。
因无OJ可评测,不知是否正确,还请帮忙检查检查有没有bug。(我自己创造的样例是没错的)
感激不尽!!
(请不要使用GPT等人工智能回答)

  • 写回答

1条回答 默认 最新

  • zsr旺财97 2024-08-27 12:13
    关注

    应该没问题(下次你可以写个对拍

    评论

报告相同问题?

问题事件

  • 创建了问题 8月27日

悬赏问题

  • ¥15 python怎么在已有视频文件后添加新帧
  • ¥20 虚幻UE引擎如何让多个同一个蓝图的NPC执行一样的动画,
  • ¥15 fluent里模拟降膜反应的UDF编写
  • ¥15 MYSQL 多表拼接link
  • ¥15 关于某款2.13寸墨水屏的问题
  • ¥15 obsidian的中文层级自动编号
  • ¥15 同一个网口一个电脑连接有网,另一个电脑连接没网
  • ¥15 神经网络模型一直不能上GPU
  • ¥15 pyqt怎么把滑块和输入框相互绑定,求解决!
  • ¥20 wpf datagrid单元闪烁效果失灵