This is the link for the 4th question of kickstart.I thought it can be done by fenwick tree but then I got that it couldn’t use Divide and conquer so I thought fenwick tree couldn’t be used…Could you help in getting the optimizzed solution fotr this…
I have doubt in this queston
I have solved this problem using segment tree.
Bro it would be easy if you just give me some overview of your code…Just tell me what info you stored in a node of segment tree and how did you combined 2 halfs to form the answer for the complete…because suppose you need to do 1 * 1 - 2 * 2 +3 * 3 -4 * 4 then anwer for 1 * 1 -2 * 2 must come from one child and answer for 3 * 3 -4 * 4 must come from another child…I want to know how did you maupulated the multiplying factors…
bro can u explain your algo…
take two leaves one will give answer 11-22 (left) and another as 13-24 (right) if u merge them then answer should be 12-23+34-45 also store the diff separately and now try to make relation between diff and the right leaf to get the actual answer
Got it bro…thanks really…ya we can observe the relation between the sum and the difference…thnx bro…