关于线段树的问题
  • 板块学术版
  • 楼主__Confringo__
  • 当前回复4
  • 已保存回复4
  • 发布时间2025/7/31 22:02
  • 上次更新2025/8/1 12:33:05
查看原帖
关于线段树的问题
1118521
__Confringo__楼主2025/7/31 22:02

最下面这是一段线段树的基础代码,实现了点修和查询区间最大值。其中第18和第19行我有时会写成

if (l == r){
    t[p] = {l,r,a[l]};
    return ;
}

但是会RE,这是为什么?

#include <bits/stdc++.h>
#define lc p << 1
#define rc p << 1 | 1
#define int long long
using namespace std;

const int N = 2e5+5;
int n,m,a[N],xx,yy;
char op;
struct Tree{
    int l,r,s;
}t[N<<2];

void pushup(int p){
    t[p].s = max(t[lc].s,t[rc].s);
}
void build(int p,int l,int r){
    t[p] = {l,r,a[l]};
    if (l == r) return ;
    int m = (l + r) >> 1;
    build(lc,l,m);
    build(rc,m+1,r);
    pushup(p);
    return ;
}
void change(int p,int x,int k){
    if (t[p].l == x && t[p].r == x){
        if (t[p].s < k) t[p].s = k;
        return ;
    }
    int m = (t[p].l + t[p].r) >> 1;
    if (x <= m) change(lc,x,k);
    else change(rc,x,k);
    pushup(p);
}
int query(int p,int x,int y){
    if (t[p].l >= x && t[p].r <= y) return t[p].s;
    int m = (t[p].l + t[p].r) >> 1,re = LLONG_MIN;
    if (x <= m) re = max(re,query(lc,x,y));
    if (y > m) re = max(re,query(rc,x,y));
    return re;
}

signed main()
{
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    build(1,1,n);
    while (m--){
        cin >> op >> xx >> yy;
        if (op == '1') change(1,xx,yy);
        else cout << query(1,xx,yy) << endl;
    }

    return 0;
}
2025/7/31 22:02
加载中...