Explanation for Stackoverflow's post on QSET

I came across this post on stackoverflow on january’15 long challenge problem QSET.But there is one thing I don’t understand in the merge function:

Node merge(Node left, Node right) {
    Node res = new Node();
    // The total sum is just the sum of the merged nodes.
    res.totalSum = (left.totalSum + right.totalSum) % 3;
    for (int i = 0; i < 3; i++) {
        res.withRemainder[i] += left.withRemainder[i];
        // Sums in the right node are shifted by left.totalSum
        res.withRemainder[(i + left.totalSum) % 3] += right.withRemainder[i];
    return res;

Should’nt there be a statement like:

   res.withRemainder[i] += right.withRemainder[i] 

in the for loop.Because we need a substring and that can be:

(i)left node string

(ii)left node string + right node string

(iii)right node string

otherwise we won’t be considering right node string alone.

If you understand it, it says that each node in segment tree will store cumulative sum of that range in ‘sum’ variable and number of 0, 1, 2 in that range.


A[] = 2, 3, 1, 5, 6, 8

Cumulative Sum ending at that index(mod 3) = 2, 2, 0, 2, 2, 1

So ‘sum’ = 1, and c[0]=0, c[1]=1, c[2]=4

Consider merging A with A,

Since ‘sum’ of left=1, c[0] in right will become c[1], c[1] will become c[2], and c[2] will be c[0] when considered for the entire range A+A.

So, sum for A+A will be 1+1 = 2, and (c[0] in merge = c[0] in left + c[2] in right) etc.

Okay so we are storing only the prefixes sum for a given range and for calculating the answer we are using the fact that:

two prefix sum will have same value if x mod 3 = 0 where x is the sum between two prefix sum.