Блог пользователя vsanjay_nitdgp

segment tree
Автор vsanjay_nitdgp, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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];

?

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My accepted solution. Hope it helps.

→ Ответить