I have very recently learned about Segment Trees and started practicing problems from cses problemset. I am now stuck on [this](https://cses.fi/problemset/task/1735/) 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);↵
}↵
}↵
~~~~~↵
↵
↵
~~~~~↵
#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);↵
}↵
}↵
~~~~~↵
↵
