CSES Range Update Queries

Debugging Help
#1

https://cses.fi/problemset/task/1651
So I have been trying to solve this problem by the way shown in the ITMO course on code forces part 2 step 1 of the Segment Tree. It was the first video.

code 
#include <bits/stdc++.h>
using namespace std;

int n,q;

template<class T> struct Seg{
    T ID; int N; vector<T> tree; 
    Seg(int N_){ N=N_+1;tree.resize(2*N,ID); }
    T comb(T a, T b){ return a+b; }
    void pull(int p){ tree[p]=comb(tree[2*p],tree[2*p+1]); }
    /* void upd(int p, T val){ tree[p+=N]=val;for(p/=2;p;p/=2) pull(p); } */
    /* T query(int l, int r){ */
    /*     T ll=ID, rr=ID; */
    /*     for(l+=N,r+=N+1;l<r;l/=2,r/=2){ */
    /*         if(l&1) ll=comb(ll,tree[l++]); */
    /*         if(r&1) rr=comb(rr,tree[--r]); */
    /*     } */
    /*     return comb(ll,rr); */
    /* } */
    void upd(int l, int r, T val){
        if(l==r){
            tree[l+=N]=val;
            return;
        }
        for(l+=N,r+=N+1;l<r;l/=2,r/=2){
            if(l&1) tree[l++]+=val;
            if(r&1) tree[--r]+=val;
        } 
    }
    T query(int r){
        T ret=tree[r+=N];
        for(r/=2;r;r/=2)
            ret+=tree[r];
        return ret;
    }
};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    Seg<long long> seg(n);
    for(int i=1,num;i<=n;i++)
        cin >> num,seg.upd(i,i,num);
    while(q--){
        int check; cin >> check;
        if(check==1){
            int a,b,u; cin >> a >> b >> u;
            seg.upd(a, b, u); 
        }
        else{
            int a; cin >> a;
            cout << seg.query(a) << '\n';
        }
    }
    /* for(int i=1;i<=n;i++) */
    /*     cout << seg.tree[i+n+1] << ' '; */
}

The code is similar to Benq’s template except I changed the query and update functions. I was wondering if I had made any small mistakes while I was modifying it.

#2

Bump

#3

In particular, it doesn’t even pass the sample case if you run it on the USACO Guide IDE (likely indicating undefined behavior).

1 Like