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.