boredom21's blog

Please help with this problem, Segtree?
By boredom21, 3 years ago, In English

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

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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:

  • $$$l \rightarrow l+1$$$: $$$kn_i := -\infty$$$ if $$$kn_i = l$$$
  • $$$r \rightarrow r+1$$$: $$$kn_i := \max(kn_i, kn_{i-a_{r+1}})$$$
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply