kar2003's blog

By kar2003, history, 11 months ago, In English

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);
    }
}
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kar2003 (previous revision, new revision, compare).

»
11 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Your code gives WA on the following test:

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.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot for the test case. I have now fixed the error and got AC on my submission.

»
11 months ago, # |
  Vote: I like it -17 Vote: I do not like it

just use segtree