Editorial for James' XOR Update

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Subtask 1

A brute-force solution would be sufficient.

Time Complexity: \mathcal O(N^2)

Full Solution

Let's first consider the following array:

0 2 0 0 0 0 0

If we take the prefix XOR of the array, we will obtain the following:

0 2 2 2 2 2 2

If we take the prefix XOR again we will obtain the following:

0 2 0 2 0 2 0

We can apply this technique to increment every other node for multiple segments in the array in \mathcal O(N) time using a similar technique as prefix-difference array.

Using the observation above, we can easily apply it on a tree using LCA.

The implementation is left for readers as an exercise.

Time Complexity: \mathcal O(Q \log N + N)


There are no comments at the moment.