如何解决_pos的越界问题

P3372 【模板】线段树 1

Ravener @ 2024-09-30 13:40:40

int n,m;
vector<int> a;

template<typename T>
class Segment_Tree
{
private:
    vector<T> _tree;
    vector<T> _lazy;
    vector<T> *arr;
#define Left(x) x<<1
#define Right(x) x<<1|1
    void maintain(int _l,int _r,int _pos)
  //这里
    {
        int _mid=_l+((_r-_l)>>1);
        if(_l!=_r && _lazy[_pos])
        {
            _lazy[Left(_pos)]+=_lazy[_pos];
            _lazy[Right(_pos)]+=_lazy[_pos];
            _tree[Left(_pos)]+=_lazy[_pos]*(_mid-_l+1);
            _tree[Right(_pos)]+=_lazy[_pos]*(_r-_mid);
            _lazy[_pos]=0;
        }
    }

    void build(int _l,int _r,int _root)
    {
        if(_l==_r)
        {
            _tree[_root]=(*arr)[_l];
            rt;
        }
        int _mid=_l+((_r-_l)>>1);
        build(_l,_mid,Left(_root));
        build(_mid+1,_r,Right(_root));
        _tree[_root]=_tree[Left(_root)]+_tree[Right(_root)];
    }

    void update(int _ul,int _ur,T _val,int _l,int _r,int _pos)
    //直接不动了qwq
    {
        if(_ul<=_l && _ur>=_r)
        {
            _tree[_pos]+=(_r-_l+1)*_val;
            _lazy[_pos]+=_val;
            rt;
        }
        int _mid=_l+((_r-_l)>>1);
        maintain(_l,_r,_pos);
        if(_l<=_mid) update(_ul,_ur,_val,_l,_mid,Left(_pos));
        if(_r>_mid) update(_ul,_ur,_val,_mid+1,_r,Right(_pos));
        _tree[_pos]=_tree[Left(_pos)]+_tree[Right(_pos)];
    }

    T sum(int _ql,int _qr,int _l,int _r,int _pos)
  //直接不动了qwq
    {
        if(_ql<=_l && _r<=_qr)
            rt _tree[_pos];
        int _mid=_l+((_r-_l)>>1);
        T _res=0;
        maintain(_l,_r,_pos);
        if(_l<=_mid) _res+=sum(_ql,_qr,_l,_mid,Left(_pos));
        if(_r>_mid) _res+=sum(_ql,_qr,_mid+1,_r,Right(_pos));
        rt _res;
    }
public:

    explicit Segment_Tree<T>(vector<T> v)
    {
        _tree.resize((n<<2)+5,0);
        _lazy.resize((n<<2)+5,0);
        arr=&v;
        build(1,n,1);
        arr=nullptr;
    }
    T range_sum(int l,int r){rt sum(l,r,1,n,1);}
    void upd(int l,int r,T val){rt update(l,r,val,1,n,1);}
};
int x,y,k,op;

signed main()
{
    n=read(),m=read();
    a.resize(n+5);
    for(int i=1;i<=n;++i)
        a[i]=read();
    Segment_Tree<int> tree(a);
    while(--m)
    {
        op=read(),x=read(),y=read();
        if(op==1)
        {
            k=read();
            tree.upd(x,y,k);
        }
        else
        {
            write(tree.range_sum(x,y));
            puts("");
        }
    }
}

by fanyixuan1010 @ 2024-09-30 19:08:37

@Ravener 线段树要开4倍空间


by fanyixuan1010 @ 2024-09-30 19:10:28

看错了,抱歉


by fanyixuan1010 @ 2024-09-30 19:16:03

if(_l<=_mid) update(_ul,_ur,_val,_l,_mid,Left(_pos));
if(_r>_mid) update(_ul,_ur,_val,_mid+1,_r,Right(_pos));

if(_l<=_mid) _res+=sum(_ql,_qr,_l,_mid,Left(_pos));
if(_r>_mid) _res+=sum(_ql,_qr,_mid+1,_r,Right(_pos));

好像有问题,判断用ql,ul


|