Сегментное дерево: Ленивое распространение

В массиве целых чисел (размер 10^5) операции похожи на эти...

  1. Выполните побитовую операцию xor с каждым элементом от индекса L до R определенным числом X
  2. Найти сумму чисел от индекса L до R.

Как я могу сделать это с сегментным деревом и ленивым распространением?

Источник

2 ответа

Решение

Я бы держал на каждом узле 32 целых числа, говорящих мне, сколько их в каждой позиции двоичного представления дочерних узлов.

Чтобы XOR узла сегмента, это просто вопрос инвертирования, сколько их в каждой позиции (для каждого бита 1 в X).

for i in range(32):
    if X&(1<<i):
        N[i] = (R-L+1)-N[i].

Чтобы рассчитать сумму,

s = 0
for i in range(32):
    s |= ((N[i]+carry)%2) << i
    carry = (N[i]+carry)/2
Источник

Ваш ответ не верный. Вам нужно выполнить какое-то ленивое обновление, как здесь: http://p--np.blogspot.ro/2011/07/segment-tree.html. Иначе, если вы выполните обновление (1,n, x) и запрос (4,5), вы получите неправильный ответ, потому что обновление изменило только корневой узел.

Источник
Другие вопросы по тегам