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
Use two pointers. At each moment, you are in some segment $$$[l, r]$$$. The knapsack should contain this information: $$$kn_i$$$ = maximum index $$$x$$$ ($$$l \leq x \leq r$$$) such that there exist a sum equal to $$$s$$$ in the segment $$$[x, r]$$$. Transitions:
Thanks for your reply, I appreciate. The main problem I'm having is to efficiently calculate if some segment has some set of elements having sum equal to S. Can u plz explain this also if u have time.
Just check $$$kn_s$$$.