### StellarSpecter's blog

By StellarSpecter, history, 3 weeks ago,

There is an array of n elements, initially filled with zeros. You need to write a data structure that processes two types of queries:

add v to the segment from l to r-1, find the sum on the segment from l to r−1.

Input The first line contains two numbers n and m (1≤n,m≤100000), the size of the array and the number of operations. The following lines contain the description of the operations. The description of each operation is as follows:

1 l r v: add v to the segment from l to r−1 (0≤l<r≤n, 0≤v≤105). 2 l r: find the sum on the segment from l to r−1 (0≤l<r≤n).

Output For each operation of the second type, print the corresponding value.

My Code:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD=1e9+7;

const int N = 1e5;
ll seg_tree[4*N];
ll lazy[4*N];

void push(int l, int r, int node){
if(l!=r&&lazy[node]!=0){
int m = l + (r-l)/2;
seg_tree[2*node]+=(m-l+1)*lazy[node];
seg_tree[2*node+1]+=(r-m)*lazy[node];
lazy[2*node+1]+=lazy[node];
lazy[2*node]+=lazy[node];
lazy[node]=0;
}
}

void update(int l, int r, int i, int j, int val, int node){
if(i>r||j<l) return;                    // OR l>r
if(i<=l&&j>=r){
seg_tree[node]+=(r-l+1)*val;
lazy[node]+=val;
return;
}
push(l,r,node);
int m = (l+r)/2;
update(l,m,i,min(j,m),val,2*node); update(m+1,r,max(i,m+1),j,val,2*node+1);
seg_tree[node]=seg_tree[2*node]+seg_tree[2*node+1];
}

ll query(int l, int r, int i, int j, int node){
if(i>r||j<l) return 0;
if(l>=i&&r<=j){             // OR if(l>=i&&r<=j) returns seg_tree[node];    -> both are correct.
return seg_tree[node];
}
push(l,r,node);
int m = (l+r)/2;
return query(l,m,i,min(j,m),2*node) + query(m+1,r,max(i,m+1),j,2*node+1);
}

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m; cin>>n>>m;
while(m--){
int t; cin>>t;
if(t==1){
int i,j,v; cin>>i>>j>>v;
update(0,n-1,i,j-1,v,1);
}
else{
int i,j; cin>>i>>j;
cout<<query(0,n-1,i,j-1,1)<<'\n';
}
}
}


24 hours and couldn't figure out what's wrong in my code. Can anyone help me decode what's wrong with my solution ? I'm getting wrong answer on test case 61 with '!' symbol.

• -14

 » 3 weeks ago, # |   0 CHAT GPT: The code appears mostly correct, but let's address some potential issues and ensure that it's working as expected. The potential reasons for a "!" symbol (which usually indicates an error in competitive programming environments) could be due to:Array Initialization: Make sure the segment tree and lazy arrays are initialized to zero. This is already handled but let's make it explicit. Proper Propagation in push function: Ensure lazy values are propagated correctly. Boundary Conditions: Handle edge cases where l or r might be at the edges of the array.:(
 » 3 weeks ago, # |   +1 seg_tree[node]+=(r-l+1)*val;Here an overflow might happen, changing val variable to long might help.
•  » » 3 weeks ago, # ^ |   0 Thanks alot mate!!!!!