Hello,
some time ago I was looking on a problem of finding number of subarrays with sum not exceeding a given number K. Numbers in the array can be negative. Right now I'm thinking if there could be an efficient solution that uses a Fenwick tree.
I know about two other solutions, one that is quite straightforward, runs in O(n^2) and uses prefixes. And the second that is an O(n log n) divide and conquer solution that uses sorted prefixes and suffixes, and solves the problem for subarrays that are on the left, on the right and those that are going trough the middle.
I also have a basic knowledge of Fenwick trees and I heard that they might be used to solve this problem. However I don't know how, apart from the fact that one might use Fenwick tree instead of prefixes in the O(n^2) solution which of course isn't very good.
TL;DR How can we use Fenwick tree/s to find number of subarrays with sum less than sum K? Numbers in the given array can be negative.
Yes, you can use a fenwick tree with range query if you compress your prefix values for NlogN solution. Alternately, (and easier), you can use an ordered set to do the queries; it's a lot less code since it's a built in data structure in C++.
Hello, Can we use two pointer ?
First, take prefix sums of the array (I'll call the array formed $$$ps$$$). Now the question is to find the number of pairs of indices $$$(i, j)$$$ s.t. $$$i < j$$$ and $$$ps[j]-ps[i] \le k$$$. This is a standard problem that can be solved easily using a Fenwick (or Segment) Tree.
Hello, Can we use two pointer ?