I am facing a problem in solving this question of CSES where we have to handle adding arithmetic progression in a range and reporting sum in a range. Can someone please take a look at my code and find the error?
My approach: For each update query, first “push” that node to correct the value of t[id] (sum) of that node. If it lies inside the query range, then lazily add (L - Lq + 1) at that node, denoting that we must add an AP in that range with the first number as lazy[id]. In push, I corrected the t[id] with the help of lazy[id] and then updated the lazy[child] accordingly. The “Query” function is quite straightforward.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX_N 200100
#define lc id<<1
#define rc id<<1|1
ll t[MAX_N<<2], lazy[MAX_N<<2], a[MAX_N], n, q;
void build(int id=1, int l=1, int r=n){
if(l==r) t[id] = a[l];
else{
int mid=(l+r)>>1;
build(lc, l, mid);
build(rc, mid+1, r);
t[id] = t[lc] + t[rc];
}
}
void push(int id, int l, int r){
if(lazy[id]){
t[id] += ((r-l+1)*(2*lazy[id]+r-l))/2;
if(l!=r)
lazy[lc] += lazy[id],
lazy[rc] += lazy[id]+(l+r)/2-l+1;
lazy[id]=0;
}
}
void update(int id, int l, int r, int lq, int rq){
push(id, l, r);
if(l>rq || r<lq) return;
if(lq<=l && r<=rq){
lazy[id] = l-lq+1;
push(id, l, r);
return;
}
int mid=(l+r)>>1;
update(lc, l, mid, lq, rq);
update(rc, mid+1, r, lq, rq);
t[id]=t[lc]+t[rc];
}
ll query(int id, int l, int r, int lq, int rq){
push(id, l, r);
if(l>rq || r<lq) return 0;
if(lq<=l && r<=rq) return t[id];
int mid=(l+r)>>1;
return query(lc, l, mid, lq, rq)+query(rc, mid+1, r, lq, rq);
}
void solve(){
cin >> n >> q;
for(int i=1; i<=n; ++i) cin >> a[i];
build();
while(q--){
int t, l, r; cin >> t >> l >> r;
if(t==1) update(1, 1, n, l, r);
else cout << query(1, 1, n, l, r) << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
}