#include <bits/stdc++.h>
using namespace std;
#define ll long long
int lazy[1000] = {0};
void updateRangeLazy(int *tree, int se, int ss, int l, int r, int incr,int idx){
//resolve lazy
if(lazy[idx]!=0){
tree[idx] +=lazy[idx];
//if not a leaf node
if(ss!=se){
lazy[2idx] += lazy[idx];
lazy[2idx+1] += lazy[idx];
}
lazy[idx] = 0;
}
//base case
//no overlap
if(l>se || r<ss){
return;
}
//complete overlap
if(ss>=l && se <= r){
tree[idx] += incr;
if(ss!=se){
lazy[2*idx] +=incr;
lazy[2*idx+1]+=incr;
}
return;
}
//recursive case
//partial overlap
int mid = (ss+se)/2;
updateRangeLazy(tree, se,mid,l,r,incr,2*idx);
updateRangeLazy(tree,mid+1,se,l,r,incr,2*idx+1);
tree[idx] = min(tree[2*idx],tree[2*idx+1]);
return;
}
int queryLazy(int *tree, int ss, int se, int qs, int qe, int idx){
//resolve lazy value at the current node
if(lazy[idx]!=0){
tree[idx] +=lazy[idx];
if(ss!=se){
lazy[2*idx] += lazy[idx];
lazy[2*idx+1] += lazy[idx];
}
lazy[idx] = 0;
}
//no overlap
if(qs>se || qe<ss){
return INT_MAX;
}
//complete overlap
if(qs>=ss && qe<=se){
return tree[idx];
}
//partial overlap
int mid = (ss+se)/2;
int leftq = queryLazy(tree,ss,mid,qs,qe,2*idx);
int rightq= queryLazy(tree,mid+1,se,qs,qe,2*idx+1);
return min(leftq,rightq);
}
void buildTree(int *a, int s, int e, int *tree, int idx){
//base case
if(s==e){
tree[idx] = a[s];
return;
}
//rec case
//left sub tree
int mid = (s+e)/2;
buildTree(a,s,mid,tree,2*idx);
buildTree(a,mid+1,e,tree,2*idx+1);
tree[idx] = min(tree[2*idx],tree[2*idx +1]);
return ;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen(“inputs.txt”,“r”,stdin);
freopen(“outputs.txt”,“w”,stdout);
#endif
int a[] = {1,3,2,-5,6,4};
int n= sizeof(a)/sizeof(int);
int *tree = new int[4*n+1];
buildTree(a,0,n-1,tree,1);
// print the tree
// for(int i=1;i<=13;i++){
// cout<<tree[i]<< " ";
// }
cout<<endl;
updateRangeLazy(tree,0,n-1,0,2,10,1);
updateRangeLazy(tree,0,n-1,0,4,10,1);
for(int i=1;i<=13;i++){
cout<<tree[i]<< " ";
}
cout<<endl;
cout<<"Q1 1-1 "<<queryLazy(tree,0,n-1,1,1,1)<<endl;
updateRangeLazy(tree,0,n-1,3,4,10,1);
cout<<"Q2 3-5 "<<queryLazy(tree,0,n-1,3,5,1);
return 0;
}