TRIQUERY - Editorial

I have a problem here: -->“How do we find num(points left of B and below G)? The answer lies in the line L1. When our sweep-line was at L1, we have: Total number of points seen so far = points either left of B or below G.”<-- I think if L1 sweep means all the points below this line in the diagram then it is “not” equal to the “points on the left of B or below G” because there can be some point b/w L2 and L1 and on the left of B which are not covered by L1 sweep. same for b/w L2 and L1 and below G. please clarify. Please also clarify the definition of line-sweep.

got it. :slight_smile: For this part of problem (refer above comment), it is a completely new BIT which is calculated from points and queries sorted by their x coordinate. see Setter’s solution for clarification.

1 Like

very nice editorial :slight_smile:

Could somebody explain me the update and read functions in the tester’s solution?

I couldn’t get this line

void update(int idx,int val,int x)

{
while (idx <= maxn) tree[x][idx]=(tree[x][idx]+val),idx += (idx & -idx);
}

What is the meaning of idx&-idx?

Could somebody help me with the editorial?
Somebody explain me the update and read functions in the tester’s solution?

I couldn’t get this line

void update(int idx,int val,int x)

{ while (idx <= maxn) tree[x][idx]=(tree[x][idx]+val),idx += (idx & -idx); }

What is the meaning of idx&-idx?

1 Like

its idx&-idx the bitwise AND operation between idx and its negation

Thanx @sparshgunner12. I finally understood whats happening.

Excellent editorial and tester’s solution.

//