QSET - Editorial-Doubt

//copied from editorial

Use segment trees. Store in node for each interval,

  • the answer for that interval

  • count1[], where count1[i] denotes number of prefixes of interval which modulo 3 give i.

  • count2[], where count2[i] denotes number of suffixes of interval which modulo 3 give i.

  • total, sum of interval modulo 3.

    can any expalin to me what is the meaning of suffixes and prefixes corresponding to a particular node


1 Like

I assume that you are familiar with Segment Tree. If not, please read about it first.

As you know, in a Segment Tree, each node represents a certain interval. Eg, if we build a Segment Tree for an array of 16 nodes, then the root represents the interval [1,16] ; the left child of root represents [1,8] ; the right child of root represents [9,16] ; and so on.
In general, if a node represents [L,R], its left child will represents the left half of [L,R] and right child will represent the right half.

Now coming to the part about prefixes and suffixes of a node. Prefixes/Suffixes of a node actually mean prefixes/suffixes of the INTERVAL of that node.
If we have a node that represents [L,R]. The prefixes of the node will be the intervals [L,L], [L,L+1], [L,L+2] ,… ,[L,R-1],[L,R] ; and the suffixes will be the intervals [R,R] , [R-1,R] , [R-2,R] , … ,[L+1,R] , [L,R]

In this question you are required to store at each node, the number of prefixes ( of the interval that is represented by that node ) whose sum%3 is 0 , whose sum%3 is 1 and whose sum%3 is 2.
This can be done by using an array prefix[3]. Same can be done for suffix.

the count1[3] of a node(that represents an interval) will have
count1[0]–>the number of prefixes whoses sum%3 will be zero
count1[1]–>the number of prefixes whoses sum%3 will be 1
count1[2]–>the number of prefixes whoses sum%3 will be 2

And the same for suffixes.am I ri8??

yes. Correct.