I have very recently learned about Segment Trees and started practicing problems from cses problemset. I am now stuck on this problem. I have tried everything from my side, please help me debug my code.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int const DEF = 0; // default value of a node
template<typename T>
struct LazySegTree {
int n;
vector<int> ops; // 1 -> delta, 2 -> assignment
vector<T> tree;
vector<T> lazy; // store updates
vector<bool> marked;
LazySegTree() : n(0) {}
LazySegTree(vector<T>& arr) : n(arr.size()) {
// size of original arr may change
while(__builtin_popcount(n) != 1) {
n++;
arr.push_back(DEF); // change the initial value
}
tree.assign(2 * n, DEF);
lazy.assign(2 * n, DEF);
ops.assign(2 * n, DEF);
marked.assign(2 * n, false);
build(arr);
}
void build(vector<T>& arr) {
for(int i = n; i < 2 * n; i++) {
tree[i] = arr[i - n];
}
for(int i = n - 1; i > 0; i--) {
tree[i] = op1(tree[2 * i], tree[2 * i + 1]);
}
}
void take(int idx, int lo, int hi, T par_val) {
// how will the update change the tree[idx] ?
if(ops[idx] == 1) {
lazy[idx] += par_val;
tree[idx] += par_val * (hi - lo + 1);
marked[idx] = true;
} else if(ops[idx] == 2){
lazy[idx] = par_val;
tree[idx] = par_val * (hi - lo + 1);
marked[idx] = true;
}
}
void push(int idx, int lo, int hi) {
// push the updates to the left and right children
if(marked[idx]) {
int mid = (lo + hi) / 2;
ops[2 * idx] = ops[2 * idx + 1] = ops[idx];
take(2 * idx, lo, mid, lazy[idx]);
take(2 * idx + 1, mid + 1, hi, lazy[idx]);
lazy[idx] = DEF;
ops[idx] = 0;
marked[idx] = false;
}
}
void update(int idx, int l, int r, int lo, int hi, T v, int op) { // last argument can be val or delta, val for assignment
if(lo > r || hi < l) return;
if(lo >= l && hi <= r) {
ops[idx] = op;
take(idx, lo, hi, v);
return;
}
push(idx, lo, hi);
int mid = (lo + hi) / 2;
update(2 * idx, l, r, lo, mid, v, op);
update(2 * idx + 1, l, r, mid + 1, hi, v, op);
// update tree[idx] here
tree[idx] = op1(tree[2 * idx], tree[2 * idx + 1]);
}
T query(int idx, int l, int r, int lo, int hi) {
if(lo > r || hi < l) return DEF;
if(lo >= l && hi <= r) {
return tree[idx];
}
push(idx, lo, hi);
int mid = (lo + hi) / 2;
return op1(query(2 * idx, l, r, lo, mid), query(2 * idx + 1, l, r, mid + 1, hi));
}
T query(int l, int r) { return query(1, l, r, 0, n - 1); }
void update(int l, int r, T v, int op) { update(1, l, r, 0, n - 1, v, op); }
T op1(T a, T b) {
// query operation
return a + b;
}
};
void solve(int test_no) {
int n, q;
cin >> n >> q;
vector<ll> arr(n);
for(auto& x : arr) cin >> x;
LazySegTree<ll> seg(arr);
int a, b, x, op;
while(q--) {
cin >> op;
if(op == 1) {
cin >> a >> b >> x;
a--, b--;
seg.update(a, b, x, 1);
} else if(op == 2) {
cin >> a >> b >> x;
a--, b--;
seg.update(a, b, x, 2);
} else {
cin >> a >> b;
a--, b--;
cout << seg.query(a, b) << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
// cin >> T;
for(int t = 1; t <= T; t++) {
solve(t);
}
}
Auto comment: topic has been updated by kar2003 (previous revision, new revision, compare).
Your code gives WA on the following test:
That is because you don't handle your updates properly, in your $$$push$$$ you could just omit the $$$assign$$$ query, by replacing it for $$$add$$$ query without actually assigning, which leads to incorrect output.
Thanks a lot for the test case. I have now fixed the error and got AC on my submission.