Изменения

Несогласованные поддеревья. Реализация массового обновления

6 байт убрано, 17:59, 7 июня 2012

→‎Псевдокод в общем виде

l = tree[node].left;

r = tree[node].right;

if [l, r)<tex>\bigcap </tex>[a, b) == <tex> \varnothing</tex>

return;

if [l, r) == <tex>\subset </tex> [a, b)

tree[node].d = tree[node].d <tex>\odot</tex> val;

return;

l = tree[node].left;

r = tree[node].right;

if [l, r)<tex>\bigcap </tex>[a, b) == <tex> \varnothing</tex>

return <tex>\perp</tex>;

if [l, r) == <tex>\subset </tex> [a, b)

return tree[node].ans <tex>\odot</tex> tree[node].d;

push(node);

~~int m = (l + r) / 2;~~ int ans = get_ans (node * 2 + 1, a, ~~ans(~~b~~, m)~~) <tex>\oplus</tex> get_ans (node * 2 + 2, ~~max(~~a~~, m)~~, b));

tree[node].ans = (tree[2 * node + 1].ans <tex>\odot</tex> tree[2 * node + 1].d) <tex>\oplus</tex>

(tree[2 * node + 2].ans <tex>\odot</tex> tree[2 * node + 2].d);

333

правки