Hi... Given an array of int and we have to find for each subarray if we can get some fixed sum S using summing some or all elements of this subarr(taking subseq not subarr). Can we do it in less than O(n*n) ? Like using segment tree or some complex data structure (I know segment tree if you can explain any approach using that It would be nice)? Please help. Thanks in advance.
I know that any of or both the children satisfy the condition then we can easily merge both the nodes but how can we merge if both child don't satisfy the above condition.
UPD: Here is the problem