Explanation for Stackoverflow's post on QSET

general
, ,
1

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.

2

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.

Ex:

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

Now,
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.

3

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.