Cer's blog

By Cer, 11 years ago, In English

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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Lazy propogation is clearly explained here with well tested and easy-to-understand code. :)

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Here's my code of the 2nd problem: http://ideone.com/ddfhfx

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this is only the update method, i think it's readable.

helper is a buffer ( helper[i] != 0, node[i] have to be updated )


void add(int left, int right, long v) { // add( root, begin of data, end of data, begin range, end range, val to add in range ) add( 1, 0, tree.length - N - 1, left, right, v ); } /** * add value val to the range [lo, hi], we are working in [rangeLo, rangeHi] **/ private void add(int node, int nodeRangeLeft, int nodeRangeRight, int left, int right, long v) { // si es un intervalo invalido, no hacer nada if ( nodeRangeLeft > nodeRangeRight || left > right || !(left >= nodeRangeLeft && right <= nodeRangeRight) ) return; // checar si los intervalos son los mismos if ( nodeRangeLeft == left && nodeRangeRight == right ) { // mismo intervalo, poner bandera al nodo setFlag( node, v ); return; } // los intervalos se cruzan tree[node] += v * ( (long)right - left + 1 ); // left range add( node << 1, nodeRangeLeft, (nodeRangeLeft + nodeRangeRight) >> 1, left, Math.min( right, (nodeRangeLeft + nodeRangeRight) >> 1 ), v ); // right range add( (node << 1) + 1, ( (nodeRangeLeft + nodeRangeRight) >> 1 ) + 1, nodeRangeRight, Math.max( left, ( (nodeRangeLeft + nodeRangeRight) >> 1 ) + 1 ), right, v ); } // set a flag to node private void setFlag(int node, long value) { if ( node >= tree.length ) return; helper[node] += value; }
»
10 years ago, # |
  Vote: I like it -16 Vote: I do not like it

//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; } }