Can someone suggest the optimal way to solve the problem "Match2" ? problem link: https://www.codechef.com/LTIME64B/problems/MATCH2 Thanks asked 30 Sep '18, 14:21

the approach i think but not sure it will work is to use fenwick tree to update in range and get cumulative sum of range 1 to N.at each index initially if A[i]==B[i] value of frequency at that index is 1 otherwise 0.so, value of initial pr will be Sum(1,n).and when updating in range if new value c==B[i],for each l<=i<=r we update frequency to 1 otherwise update frequency to zero. i learned recently about binary indexed tree so, not confident about approach.if there is any mistake or in scenarios where to use binary indexed tree correct me with explanation. answered 30 Sep '18, 15:27
Hi @abhi55, I am unable to understand, "when updating in range if new value c==B[i],for each l<=i<=r we update frequency to 1 otherwise update frequency to zero." this line of your explanation. Are you trying to say that we need to run another loop from l<=i<=r to compute this, if yes then this solution is almost like brute force ?? Please correct me if i am wrong. Thanks
(30 Sep '18, 18:30)
