这是修改过的:
```
#include<cstring>
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
#define INF 0x3f3f3f3f
#define N 200005
#define LL long long
#define lc u<<1 //乘二
#define rc u<<1|1 //乘二+1
int w[N];
struct Tree
{
LL l,r,sum; //线段树 懒标记是0和1
}tr[N*4];
void update(int u){
tr[u].sum = min(tr[u*2].sum, tr[u*2+1].sum);
}
void build(LL u,LL l,LL r) //建树 (父节点,左端点,右端点)
{
tr[u]={l,r,w[l]};
if(l==r) return;
LL m=l+r>>1; //除二
build(lc,l,m);
build(rc,m+1,r);
update(u);
}
LL query(LL u,LL l,LL r,int x,int y){ //区间查找(输出) (父节点,总左端点,总右端点)
LL max=INF;
if((x <= l) && (r <= y)) return tr[u].sum;
else if((y < l) || (r < x)) return INF;
if(tr[u].r==tr[u].l) return tr[u].sum;
LL m=(tr[u].l+tr[u].r)>>1; //除二
if(l<=m) max=min(max,query(lc,l,m,x,y));
if(r>m) max=min(max,query(rc,m+1,r,x,y));
return max;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m,x,y;
cin>>n>>m;
for(int i=1;i<=n;++i)
{
cin>>w[i];
}
build(1,1,n);
while(m--)
{
cin>>x>>y;
cout<<query(1,1,n,x,y)<<' ';
}
return 0;
}
```
by chillLee @ 2023-11-02 18:05:39
线段树的 `query` 操作通常需要判断被查询区间是否被包含在要求区间内,如果包含直接返回,这样可以避免查询更多的子节点。
您的代码没有这样的判断,那么在查询时本质上是把区间内所有的子节点全部遍历了一遍,没有起到线段树维护区间性质以避免遍历子节点总而大幅降低复杂度的这个效果。
by chillLee @ 2023-11-02 18:07:39
这是修改过的,可以 `AC` 。
刚刚发的忘记标哪里改动了,现在给您标出来。
```
#include<cstring>
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
#define INF 0x3f3f3f3f
#define N 200005
#define LL long long
#define lc u<<1 //乘二
#define rc u<<1|1 //乘二+1
int w[N];
struct Tree
{
LL l,r,sum; //线段树 懒标记是0和1
}tr[N*4];
// update()函数维护父节点的正确区间性质。
void update(int u){
tr[u].sum = min(tr[u*2].sum, tr[u*2+1].sum);
}
void build(LL u,LL l,LL r) //建树 (父节点,左端点,右端点)
{
tr[u]={l,r,w[l]};
if(l==r) return;
LL m=l+r>>1; //除二
build(lc,l,m);
build(rc,m+1,r);
update(u);
}
// query 函数进行了改动
LL query(LL u,LL l,LL r,int x,int y){ //区间查找(输出) (父节点,总左端点,总右端点)
LL max=INF;
if((x <= l) && (r <= y)) return tr[u].sum;
else if((y < l) || (r < x)) return INF;
if(tr[u].r==tr[u].l) return tr[u].sum;
LL m=(tr[u].l+tr[u].r)>>1; //除二
if(l<=m) max=min(max,query(lc,l,m,x,y));
if(r>m) max=min(max,query(rc,m+1,r,x,y));
return max;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m,x,y;
cin>>n>>m;
for(int i=1;i<=n;++i)
{
cin>>w[i];
}
build(1,1,n);
while(m--)
{
cin>>x>>y;
cout<<query(1,1,n,x,y)<<' ';
}
return 0;
}
```
by chillLee @ 2023-11-02 18:16:37
@[chillLee](/user/706209) 谢谢您,关注了
by RingTouSou @ 2023-11-02 18:26:49