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