In order to solve this problem, we need to use the properties of binary operation XOR. More concisely, the XOR sum of N bits provides the parity of N.
In each node we will store a binary array of length SIGMA (26 - the size of the alphabet). The ith bit is 1 if the ith letter appears an odd number of times, and 0 otherwise.
Let's take two nodes x and y. Let us use the following notation:
- x(1), x(2), …, x(L1) - the array of nodes on the chain from 1 to x , where x(1) = 1 and x(L1) = x.
- y(1), y(2), …, y(L2) - analoguely.
Also, let mask[x] = info[x(1)] ^ info[x(2)] ^ … ^ info[x(L1)]. The same goes for mask[y].
Let lca = LCA(x, y) (the lowest common ancestor of x and y). There exists one pair (i, j) such that:
- 1 ≤ i ≤ L1
- 1 ≤ j ≤ L2
- x(i) = lca = y(j)
We take a number A. We know that A ^ A = 0, so:
mask[x] ^ mask[y] = XOR_SUM(x(p), i < p ≤ L1) ^ XOR_SUM(y(q), j < q ≤ L2)
lca lies on the chain from x to y, so the answer would be mask[x] ^ mask[y] ^ info[lca].
For any update, the mask can be calculated in contant time. The only problem left is finding the LCA in a changing tree.
This can be achived in O(sqrt(N)) or O(log(N)) (see: Stramosi).