Pull to refresh

Comments 6

Первоисточник, по всей видимости, Bentley. А мой комментарий означал не «украдено отсюда», а «уже было на хабре».
Честно говоря, эта статья получше, та слишком сухая какая-то
Расход памяти должен быть 4*n, а в коде он 2*n, аккуратнее надо.
И вообще, раз уж приведен рекурсивный вариант поиска функции на отрезке, то и модификацию наверное тоже имело смысл написать рекурсивно.
Идея такая:
modify(pos,val,l = 0,r = MAX_N-1,p=1)
...if (l==r) tree_data[p] = val;
...else
......m = (l+r)/2;
......if pos <= m
.........modify(pos,val,l,m,p*2);
......else
.........modify(pos,val,m+1,r,p*2+1);
......treedata[p] = max(treedata[2*p], treedata[2*p+1])
Sign up to leave a comment.

Articles