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

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

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

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


algorithm data-structures segment-tree
person palatok    schedule 11.11.2012    source источник
comment
Я добавлю подсказку: XOR ассоциативен. (A XOR X) XOR Y) имеет тот же результат, что и A XOR (X XOR Y).   -  person Patricia Shanahan    schedule 11.11.2012
comment
@Patricia Shanahan, спасибо, но я знала это. моя проблема состоит в том, чтобы узнать сумму сегмента.   -  person palatok    schedule 11.11.2012
comment
Ваша проблема состоит в том, чтобы найти сумму данных сегмента, которая также подлежит XOR на сегментах. Как бы вы решили проблему, если бы у вас была только операция 2?   -  person Patricia Shanahan    schedule 11.11.2012

Ответы (2)


arrow_upward
1
arrow_downward

Я бы оставил на каждом узле 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
person Juan Lopes    schedule 12.11.2012
comment
я не понимаю эту строку... N[i] = (R-L+1)-N[i]. зачем мне вычитать N[i] ? - person palatok; 13.11.2012
comment
Чтобы инвертировать количество единиц в сегменте. Предположим, у нас есть отрезок от 3 до 7 с 2 единицами. Это означает, что операция xor с битом 1 инвертирует это число, т. е. все единицы станут нулями, а все нули станут единицами. 7-3+1-2=5-2=3 - person Juan Lopes; 13.11.2012

arrow_upward
1
arrow_downward

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

person Octavian Ganea    schedule 24.02.2013