I'm learning segment tree data structure and I've learned the (Build, update, query) functions,and I'm trying to make an update on an interval using lazy propagation algorithm but I can't find the correct implementation of it.
Would you please provide me with the correct code of lazy propagation algorithm for these two problem :
1- we have an array of integers and there are two queries :
a- get the sum of a specific range from the array
b- modify a specific range in the array by adding a number to all elements in this range
2- we have an array of integers and there are two queries :
a- get the minimum number of a specific range from the array
b- modify a specific range in the array by adding a number to all elements in this range
I just need an "update" function on a range. Thanks.
Lazy propogation is clearly explained here with well tested and easy-to-understand code. :)
Here's my code of the 2nd problem: http://ideone.com/ddfhfx
this is only the update method, i think it's readable.
helper is a buffer ( helper[i] != 0, node[i] have to be updated )
//use structure to store maxval and value updated at that index //take offset as well as value to get answer within the updated range
include < cstdio >
include < iostream >
using namespace std;
define INF 1e9
struct Node { int offt; int cmax; } tree[5000];
void update(int n, int b, int e, int i, int j, int val) { if (b>e || i>j || b>j || e
if (b>=i && e<=j) { tree[n].offt += val; tree[n].cmax += val; return; }
update(n*2 , b , (b+e)/2 , i , j , val); update(n*2+1 , (b+e)/2 + 1 , e , i , j , val);
tree[n].cmax = max ( tree[n*2].cmax , tree[n*2+1].cmax ) + tree[n].offt; }
int query(int n, int b, int e, int i, int j, int offt) { if (b>e || i>j || b>j || e
if (b>=i && e<=j) return tree[n].cmax + offt; //the increment of current node is already added to cmax here (see update function)
offt += tree[n].offt; return max ( query(n*2 , b , (b+e)/2 , i , j, offt) , query(n*2+1 , (b+e)/2 + 1 , e , i , j, offt) ); }
int main() { int tc,x,a,b,v; cin >> tc; while(tc--) { cin >> x >> a >> b; if ( x == 0 ) { cin >> v; update(1,0,999,a,b,v); } else cout << query(1,0,999,a,b,0) << endl; } }