vsanjay_nitdgp's blog

segment tree
By vsanjay_nitdgp, history, 9 years ago, In English

i used the following lazy propogation to update my tree...like i wanted to get sum of [i,j]

http://ideone.com/Vh05zS

my input was n=8;all elements set to zero.'0'.

then i gave my array number 26 to update array from i=1 to i=3;[1,3]

but i am getting tree[1]=52 instead of 78....

could any one say where i am getting wrong.....

thanks in advance

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why in function bt you do this :

 bt(1,a,(a+b)/2);
 bt(1,(a+b)/2+1,b);

instead this:

 bt(2*node,a,(a+b)/2);
 bt(2*node+1,(a+b)/2+1,b);
 tree[node] = tree[node*2] + tree[1+node*2];

?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My solution in c++. I coded this long time ago.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My accepted solution. Hope it helps.

→ Reply