更改了线段树实现的方式,将lazy值作为单独的节点存在,降低存储压力
struct Node{
long long sum;
Node():sum(0ll){}
Node operator +(const Node& other){
Node res = *this;
res.sum += other.sum;
return res;
};
void applyLazy(lazyNode& value, int length){
this->sum += 1ll * value.add * length;
}
};
template<typename T>
class SegmentTree{
public:
SegmentTree(const vector<T>& s): sz_(int(s.size() - 1)){
st_.resize(4 * sz_);
lazy_.resize(4 * sz_);
build(s, 1, 1, sz_);
}
void update(int i, int j, lazyNode value){
update(1, 1, sz_, i, j, value);
}
long long query(int i, int j){
return query(1, 1, sz_, i, j).sum;
}
private:
vector<T> st_;
vector<lazyNode> lazy_;
int sz_;
const lazyNode flag_{};
void update(int p, int l, int r, int i, int j, lazyNode value){
propagate(p, l, r);
if (i > j){
return;
}
if (l >= i && r <= j){
lazy_[p] = value;
propagate(p, l, r);
return;
}
int mid = (l + r) >> 1;
update(p << 1, l, mid, i, min(mid, j), value);
update(p << 1 | 1, mid + 1, r, max(mid + 1, i), j, value);
st_[p] = st_[p << 1] + st_[p << 1 | 1];
};
T query(int p, int l, int r, int i, int j){
propagate(p, l, r);
if (l >= i && r <= j){
return st_[p];
}
int mid = (l + r) >> 1;
if (j <= mid) {
return query(p << 1, l, mid, i, j);
}
else if (i > mid) {
return query(p << 1 | 1, mid + 1, r, i, j);
}
else {
return (query(p << 1, l, mid, i, mid) + query(p << 1 | 1, mid + 1, r, mid + 1, j));
}
}
void build(const vector<T>& s, int p, int l, int r){
if (l == r){
st_[p] = s[l];
}
else{
int mid = (l + r) >> 1;
build(s, p << 1, l, mid);
build(s, p << 1 | 1, mid + 1, r);
st_[p] = st_[p << 1] + st_[p << 1 | 1];
}
}
void propagate(int p, int l, int r){
if (lazy_[p] != flag_){
st_[p].applyLazy(lazy_[p], r - l + 1);
if (l != r){
lazy_[p << 1] |= lazy_[p];
lazy_[p << 1 | 1] |= lazy_[p];
}
lazy_[p] = flag_;
}
}
};
void solve(){
int n, q;
cin >> n >> q;
vector<Node> a(n + 1);
for (int i = 1; i <= n; ++i){
cin >> a[i].sum;
}
SegmentTree<Node> st(a);
while (q --){
int k, x, y;
cin >> k >> x >> y;
if (k & 1){
long long t;
cin >> t;
st.update(x, y, lazyNode(t));
}
else{
cout << st.query(x, y) << '\n';
}
}
}
可以考虑在线段树初始化时lazyNode也作为模板类进行设置,当使用C语言变量时,可能会增加通用性。
标签:Node,sz,洛谷,int,线段,long,lazyNode,p3372,sum From: https://www.cnblogs.com/yxcblogs/p/18145343